Congruences

From Wikiversity
Jump to navigation Jump to search

Congruences[edit | edit source]

The subject of congruences is a field of mathematics that covers the integers, their relationship to each other and also the effect of arithmetic operations on their relationship to each other.

Expressed mathematically:

read as: A is congruent with B modulo N.

are integers and

This means that:

  • A modulo N equals B modulo N,
  • the difference, A-B, is exactly divisible by N, or

where p modulo N or p % N is the remainder when p is divided by N.

For example: because division is exact without remainder, or

Similarly, because division is not exact, or

Law of addition[edit | edit source]

Adding a constant[edit | edit source]

If then:

Proof:

, therefore

which is exactly divisible by N.

Adding 2 congruences[edit | edit source]

If and then:

Proof:

, therefore and

which is exactly divisible by N.

Law of Common Congruence[edit | edit source]

If and

then:

Proof:

and

which is exactly divisible by N.

Law of Multiplication[edit | edit source]

by a constant[edit | edit source]

If then:

Proof:

which is exactly divisible by N.

by another congruence[edit | edit source]

If and

then:

Proof:

and

which is exactly divisible by N.

Law of squares[edit | edit source]

If then:

Proof:

which is exactly divisible by N.

Law of Division?[edit | edit source]

A simple example shows that a "law of division" does not exist.

However

Because is not exactly divisible by

Quadratic Congruences[edit | edit source]

Introduction[edit | edit source]

A quadratic congruence is a congruence that contains at least one exact square, for example:

or

Initially, let us consider the congruence:

If then:

Proof: which is exactly divisible by

Consider an example with real numbers.

Let and

N = 257
6 -221
7 -208
8 -193
9 -176
10 -157
11 -136
12 -113
13 -88
14 -61
15 -32
16 -1
17 32
18 67
19 104
20 143
21 184
22 227
23 272
24 319
25 368
26 419

A cursory glance at the values of indicates that the value is never divisible by

Proof: therefore or

The table shows all possible values of and

As you can see, the value is never exactly divisible by

If you look closely, you will see also that it is never exactly divisible by or

However, you can see at least one value of exactly divisible by and at least one value of exactly divisible by

The table shows all possible values of and

The two lines marked by an show values of exactly divisible by The two values of and or are solutions of the congruence.

Why are values of divisible by some primes and not divisible by other primes? An interesting question that leads us to the topic of quadratic residues.

Quadratic Residues[edit | edit source]

Consider all the congruences for prime number

for

0 0 0
1 1 1
2 4 4
3 9 4
4 16 1

Quadratic residues of are

Values are not quadratic residues of These values are quadratic non-residues.

To calculate the quadratic residues of a small prime

# python code:
def quadResidues(p) :
    L1 = []
    for	v in range (p>>1, -1, -1) :
      	L1 += [(v*v) % p]
    return L1

print (quadResidues(11))
[3, 5, 9, 4, 1, 0]

Quadratic residues of are

The method presented here answers the question, "What are the quadratic residues of p?"

If is a very large prime, the question is often, "Is r a quadratic residue of p?" The answer is found in advanced number theory.

Let us return to quadratic residues mod

therefore is not a quadratic residue of This is why is never divisible by exactly.

therefore is a quadratic residue of and a value of that satisfies the congruence has form

From the table above:

N = 257
9 -176
13 -88
20 143
24 319

These values of are exactly divisible by

is

is

is

is

Products[edit | edit source]

This section uses prime number as an example.

Using quadResidues(p) quadratic residues of are:

qr41 = [0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40]

Quadratic non-residues of are:

qnr41 = [3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 29, 30, 34, 35, 38]

of 2 residues[edit | edit source]

A simple test to verify that the product of 2 residues is a residue:

# Python code.
for index1 in range (0, len(qr41)) :
    v1 = qr41[index1]
    for index2 in range (index1, len(qr41)) :
    	v2 = qr41[index2]
	    residue = (v1*v2) % 41
	    if residue not in qr41 : print ('residue',residue,'not quadratic.')

This test shows that, at least for prime number the product of 2 residues is a residue. Advanced math proves that this is true for all primes.

of 2 non-residues[edit | edit source]

A simple test to verify that the product of 2 non-residues is a residue:

# Python code.
for index1 in range (0, len(qnr41)) :
    v1 = qnr41[index1]
    for index2 in range (index1, len(qnr41)) :
	    v2 = qnr41[index2]
	    residue = (v1*v2) % 41
	    if residue not in qr41 : print ('residue',residue,'not quadratic.')

This test shows that, at least for prime number the product of 2 non-residues is a residue. Advanced math proves that this is true for all primes.

of residue and non-residue[edit | edit source]

A simple test to verify that the product of residue and non-residue is non-residue:

# Python code.
for index1 in range (1, len(qr41)) :
    v1 = qr41[index1]
    for index2 in range (0, len(qnr41)) :
        v2 = qnr41[index2]
        residue = (v1*v2) % 41
        if residue not in qnr41 : print ('residue',residue,'quadratic.')

This test shows that, at least for prime number the product of residue and non-residue is non-residue. Advanced math proves that this is true for all primes.

Some authors may consider as not a legitimate residue.

is not included as a residue in the test above.

Euler's criterion[edit | edit source]

In number theory, Euler's criterion is a formula for determining whether or not an integer is a quadratic residue modulo a prime number. Precisely,

Let p be an odd prime and a be an integer coprime to p. Then

Euler's criterion can be concisely reformulated using the Legendre symbol:


It is known that is a quadratic residue modulo

Therefore should be

# python code:
>>> (3**5) % 11
1

It is known that is a quadratic non-residue modulo

Therefore should be

# python code:
>>> (7**5) % 11
10

Python's decimal module provides a method for computing very efficiently for both small and very large numbers.

# python code:
>>> import decimal
>>> decimal.Context().power(3,5,11)
Decimal('1')
>>> decimal.Context().power(7,5,11)
Decimal('10')
>>>
>>> a = 3456789
>>> p = 761838257287
>>> decimal.Context().power(a, p>>1, p)
Decimal('761838257286')

Value is not a quadratic residue modulo

An exact square such as is always a quadratic residue modulo an odd prime

Product of 2 residues[edit | edit source]

Let be quadratic residues modulo odd prime

Let

Then:

By law of multiplication:

or


Product of 2 quadratic residues is quadratic residue.

Similarly, product of 2 non-residues is residue, and product of residue and non-residue is non-residue.

Factors of integer N[edit | edit source]

Several modern methods for determining the factors of a given integer attempt to create two congruent squares modulo integer

This means that the difference between the two squares is exactly divisible by :

Integer always contains the factors called trivial factors.

If contains two non-trivial factors then:

With a little luck and in which case:

and where

"" is function ""

A simple example:[edit | edit source]

We will use quadratic congruences to calculate factors of for

Right hand side exact square[edit | edit source]

One congruence produced an exact square for y:

70 4900 729


Non-trivial factors of are

Right hand side negative[edit | edit source]

Table below contains a sample of values of that produce negative

7 49 -4122
8 64 -4107**
9 81 -4090
10 100 -4071
11 121 -4050!!
12 144 -4027
60 3600 -571
61 3721 -450!!
62 3844 -327
63 3969 -220
64 4096 -75**
Non-trivial result 1[edit | edit source]

The congruences:

8 64 -4107**
64 4096 -75**

Non-trivial factors of are

Non-trivial result 2[edit | edit source]

The congruences:

11 121 -4050!!
61 3721 -450!!

Non-trivial factors of are

Right hand side positive[edit | edit source]

Table below contains a sample of values of that produce positive

65 4225 54**
66 4356 185
88 7744 3573
89 7921 3750**!!
90 8100 3929
144 20736 16565
145 21025 16854!!
146 21316 17145
Non-trivial result[edit | edit source]

The congruences:

65 4225 54**
89 7921 3750**!!

Non-trivial factors of are

Trivial result[edit | edit source]

The congruences:

89 7921 3750**!!
145 21025 16854!!

This congruence produced the trivial factors of

With 3 congruences[edit | edit source]

The congruences:

56 3136 -1035
59 3481 -690
145 21025 16854


Non-trivial factors of are

Links to related topics[edit | edit source]

Quadratic Residue

Modular Arithmetic

Leonhard Euler, Euler's Criterion

Adrien-Marie Legendre, Legendre Symbol

Carl Friedrich Gauss, Triple_bar or , Quadratic reciprocity

Carl Pomerance, Quadratic sieve

Greatest common divisor, Greatest common divisor (Example of Recursion)

Python's decimal Module