Congruences

Basic concepts

Congruence of numbers

Attempts to solve indeterminate Diofant's equations inspired introduction of so called congruences.

If the number r divides the difference a-b, then the numbers a,bεZ are congruent with respect to r. Number rεN is called the "module".
Numbers congruent relative to composite module are also congruent with respect to any divisor of this module.

Expression that contains two congruent variables in the form of equation (with symbol ≡) is called congruence. When a≡b (mod r), then (for a, b, cεZ) the following applies:

 a+c ≡ b+c (mod r),   a−c ≡ b−c (mod r),  a∙c ≡ b∙c (mod r) 

Dividing both sides of congruence is only possible by number c incommensurable with the module r, (c, r) = 1:

 a/c ≡ b/c (mod r) 

In the case where c|a, c|b, c|r it is possible to shorten the entire congruence:

 a/c ≡ b/c (mod r/c) 

Solution of congruences

All algebraic congruences with one unknown can be converted to form X≡0, where X is an algebraic function of the variable X containing no fractions.
Congruence a_k∙x^k + a_k−1∙x^k−1 + ... + a₁∙x + a₀ ≡ 0 (mod r) has either infinitely many solutions, or no more than k solutions.

Solutions of congruences writes analogically as solutions of equations. For simple linear congruences ax ≡ b (mod r): x≡b/a and for congruences of higher degrees x^k ≡ c (mod r): x≡ √c (mod r) [Gauss,I].

Congruence according to complex module

All numbers that occupy the same position relative to the square coordinate system (0xY) are mutually congruent.
E.g. in the net of multiples of numbers (2 + i), the point i lay in the lower left corner of the square {0, 2+i, 1+3i, -1+2i}. The same position occupies point 3 inside the square {3-i, 5,4 + 2i + 2 i}. Therefore i ≡ 3 mod (2 + i).

Congruence of polynomials

Polynomials P=a+bx+cx²+dx³+... and P'=a'+b'x+c'x²+d'x³+... calls congruent according to module r, when the coefficients at identical degrees x are congruent (i.e. a≡a 'b≡b', ... mod r). For polynomials in most cases the same is true as for numbers.

The ratio R/P according to a given module is the polynomial Q, if PQ≡R. All polynomials congruent with Q are regarded in this case as one single polynomial. In some cases, however, the ratio may have several (incongruent) values. [Gauss II]

Simple binomial congruence

Definition

Congruence of the form x^h−1 ≡ 0 (mod p) is called binomial congruence. While the binomial equations x^h−1 = 0 have always h (or infinitely many) solutions, for binomial congruence this need not to be. According to the Little Fermat's theorem is: x^p−1−1 ≡ 0 (mod p) (for pεP). For binomial congruence - the cycle of roots of length h is supplemented by cycle of the Little Fermat theorem (see).

Congruence x^h−1 ≡ 0 (mod p) has always (h, p-1) = s roots and these roots correspond to solution of the congruence x^s−1 ≡ 0 (mod p):

 Congruence  x³ mod 7               Congruence  x4mod 7     
  has (3,6) = 3 solutions              has (4,6) = 2 solutions
───────────────────────────         ───────────────────────────
x³       0 1 8 27 64 125 216        x4         0 1 16 81 256 625 1296
x³ mod 7 0 1 1  6  1   6   6        x4mod 7    0 1  2  4   4   2    1
                                    ───────────────────────────
                                    x²            0 1 4 9 16 25  36
                                    x² mod 7      0 1 4 2  2  4   1  

Cycle of binomial congruence

The greatest common divisor of exponent h and number p-1 (module p reduced by one) is called cycle of congruence, c = (h, p-1).

Suitable modules

We will consider as an appropriate module such a prime p that does not disrupt the cycle of the equation h. Such property have numbers p for which h|(p−1), i.e. (h, p-1) = h. Suitable modules are therefore prime numbers of the form t∙h+1 (tεN).
E.g. for equation x⁷−1=0 is the first suitable prime number p=29, because numbers 1∙7+1=8, 2∙7+1=15 and 3∙7+1=22 are composite.

G-systems with prime order

In the following list lines of selected G-systems with prime order k and module r=n^k−1 are listed.

 G(2,1)    G(2,2)     G(2,3)       ...
   1        1  2       1  2  4         
                       3  6  5    

From the product of expressions (x-u), where u are the individual instances, we get polynomials congruent with the term x^r−1:

  G(2,1):   (x−1)           = x−1            ≡ x −1 (mod 1)
  G(2,2):   (x−1)(x−2)      = x²−3x+2        ≡ x²−1 (mod 3)
  G(2,3):   (x−1)(x−2)(x−4) = x³− 7x²+14x− 8 ≡ x³−1 (mod 7)
            (x−3)(x−6)(x−5) = x³−14x²+63x−90 ≡ x³−1 (mod 7) 

Decomposition of congruence

Solution of congruence x^h−1 ≡ 0 (mod p) depends on the decomposition of numbers E = φ (h) to multiple of primes. Let the decomposition of number E is E=∏pi^di. Then it is possible to build Σdi congruences of lower levels, while always di congruences has degree pi. E.g. let us consider a congruence x³¹−1≡0 (mod p). A suitable module is a prime of the form p = b∙r + 1 (see above). In the sequence 32,63,94,125,156,187,218,249,280,311,342 ... is the first such suitable number p = 311.

For congruence x³¹−1 ≡ 0 (mod 311) is E=φ(31)=30=2¹∙3¹∙5¹. Solutions must be converted to 3 congruences: of the second, third and fifth degree.

The use of primitive roots

When compiling periods Gauss uses primitive roots. Let us seek such number z of whose powers z^h (mod r) pass (for h = 0,1,2, .., φ(r)), all the numbers relatively prime with r, ie. the primitive root of the equation z^φ(r) ≡ 1 (mod r). And let as write the sequence of numbers z^h (mod r) in the table as follows. We will mark the table rows by i = 0,1, .., (e-1), the table columns j = 0,1, ... (k-1) and denote h=j∙e+i. Numbers in the thus obtained periods correspond (with the exception of the rank) to instances of R (6,6,31)

 j=0  j=1 j=2 j=3 j=4 j=5                   R(6,6,31)
 i=0   1  26  25  30   5   6  (0/5)         1   6   5  30  25  26
 i=1   3  16  13  28  15  18  (1/5)         2  12  10  29  19  21
 i=2   9  17   8  22  14  23  (2/5)         3  18  15  28  13  16
 i=3  27  20  24   4  11   7  (3/5)         7  11   4  24  20  27
 i=4  19  29  10  12   2  21  (4/5)         8  17   9  23  14  22 

System R(6,6,31), e= φ(r)/k=30/6=5, consists of the following periods:

    1
    x  + x6  + x5  + x30 + x25 + x26 = s(5,0)
    x2 + x12 + x10 + x29 + x19 + x21 = s(5,1)
    x3 + x18 + x15 + x28 + x13 + x16 = s(5,2)
    x7 + x11 + x4  + x24 + x20 + x27 = s(5,3)
    x8 + x17 + x9  + x23 + x14 + x22 = s(5,4)
    x31−1

Composite binomial congruence

Generalization of primitive roots

So far we have been looking for a primitive roots of prime modules r. Now we want to expand their definition on the composite modules. Here we can not (as with rεP) to select systems with the order k= r−1. Such systems indeed does not exist. Therefore let us seek the systems with the highest possible order.

  R(2,6,9)                       R(5,6,9)
   0                              0  
   1   2   4   8   7   5          1   5   7   8   4   2
   3   6                          3   6
   9                              9

It seems that the original definition of primitive roots may be generalized by replacement of order k= r−1, by order k=φ(r). Also here degrees of the systems (as in our example, 2 and 5) gets the meaning of primitive roots (according to module r). The number of systems with the given order k is φ (k) = φ (φ (r)).

Systems with order k=φ(r) does not exists always, for example they does not exists for module r=8 [see Universal exponent]. They exists only for modules r=2,4,p^e and 2∙p^e, where pεP and eεNo.

Product of primitive roots

When the module r has a primitive root, then the following applies: (Gauss,1801, $78)

 ∏(a) ≡ −1 mod r (for 1<a<r, (a,r)=1) 

Otherwise is:

 ∏(a) ≡ +1 mod r (for 1<a<r, (a,r)=1) 

Divisibility

Solution of binomial congruence (for pεP)   x^r−1 ≡ 0 (mod p)

relates to divisibility of expression M(x,r).

Expression x^r−1 is divisible by x^q−1 when q|r.

Let us rewrite schema of the system G(2,4) = R(2,4,15) such way, that instance numbers will be placed into exponents of variable x:

   1−1
   x−1     x2−1      x4 −1     x8 −1
   x3−1    x6−1      x12−1     x9 −1      (mod p)
   x5−1    x10−1
   x7−1    x14−1     x13−1     x11−1
   x15−1

Expressions whose exponents q are relative prime to r, i.e. (q,r)=1, can not be divisible with M(x,r).

Therefore, M(x,y) is not divisible by any of the expressions:

   x−1     x2−1      x4 −1     x8 −1
   x7−1    x14−1     x13−1     x11−1

These expressions we call primitive roots. The number of primitive roots is determined by Euler function: E=φ(r). In a system with order k forms the expressions e=E/k = φ(r)/k classes. In our example E=φ(15)=8, e=φ(15)/4=8/4=2.

Structure of the solution

Let as consider a composite binomial congruence x⁶−1 ≡ 0 (mod 35). At the same time applies:

   Congruence     Cycle     Solution
   (1) x6−1 ≡ 0 (mod 5)  (6,5−1) = 2    1,4
   (2) x6−1 ≡ 0 (mod 7)  (6,7−1) = 6    1,2,3,4,5,6

There are 2∙6 = 12 solutions. Solutions can be determined e.g. by the relation x= 7u∙x₁ − 5v∙x₂, where x₁,x₂ are distinct solutions of congruences (1)(2) and numbers u,v are selected so, that 7u−5v = 1.

E.g.for u=3, v=4 is 7∙3−5∙4 = 1 a x=21∙x₁−20∙x₂. Hence xε{1,4,6,9,11,16,19,24,26,29,31,34}.

Order of the solution

Solution x is of order d, when x^d ≡ 1 (mod p), for d|r.

x       1  6  29  34  11  16   4   9  19  24  26  31
────────────────────────────────────────────────────────────  
x2      -  1   1   1  16  11  16  11  11  16  11  16
x3                     1   1  29  29  34  34   6   6
x4                            11  16  16  11  16  11
x5                             9   4  24  19  31  26
x6                             1   1   1   1   1   1

Order  Roots                  Number  
────────────────────────────────────
  1    1                        1
  2    6, 29, 34                3
  3    11, 16                   2 
  6    4, 9, 19, 24, 26, 31     6

Self and nested solutions

For every order represents the number of roots the number of self solutions. Total number of solutions (including nested) gives the following scheme:

 Order Total solutions     Nested solutions   Self solutions           
───────────────────────────────────────────────────────────
 1  (1,5−1) ∙ (1,7−1) = 1∙1 =  1       0               1
 2  (2,5−1) ∙ (2,7−1) = 2∙2 =  4       1               3
 3  (3,5−1) ∙ (3,7−1) = 1∙3 =  3       1               2
 6  (6,5−1) ∙ (6,7−1) = 2∙6 = 12       1+3+2=6         6

Product of solutions

Product of all solutions that meet the congruence x^r−1 ≡ 0 (mod p) is according to module p congruent with the number one.

In our example is:  1∙4∙6∙9∙11∙16∙19∙24∙26∙29∙31∙34 = 13776637095936 = 393618202741 ∙ 35 + 1.

From the roots we can also set up sets (1), (4,9), (11,16), (19,24), (26,31), (6,29,34), where inside each is a product of the numbers ≡ 1 (according to module p).

Distinction of cases

When the number r is composite, then not all the roots of congruence belongs to x^r−1≡0 of the given system R(n,k,r), but they nests from other systems.
E.g. equation x¹⁵−1=0 shares the roots with x⁵−1=0 and x³−1=0 because x¹⁵−1 is divisible by x⁵−1 and also x³−1. Therefore it is possible to restrict examining to only cases where r is prime or power prime numbers. Let r=t^ν, where tεP. Then E=φ(r)=φ(t^ν)=(t−1)∙t^ν−1 = r∙(t−1)/t.

Power expressions

Sum of the powers x^u

Instances of system R(n,k,r) pass all the numbers 0,..,r−1. Powers x^u make geometrical sequence with sum: ∑x^u = (x^r−1)/(x−1) = M(x,r)

For R(2,3,7) is 1+x+x²+x³+x⁴+ x⁵+x⁶ = (x⁷−1)/(x−1) = M(x,7).

Residues by module M(x,r)

Powers x^s (for sεN) give according to module x^r−1 residues of the same form, i.e. e.g. x^u (uεN, u<s). The following applies s ≡ u (mod r):  x^s ≡ x^u (mod x^r−1)  <==> s ≡ u (mod r)

E.g. x⁸ ≡ x³ (mod M(x,5)), for x=3: 6561 ≡ 27 (mod 242).

Because x^r−1 is product M(x,r), also applies:

 x^s ≡ x^u (mod M(x,r)) <==> s ≡ u (mod r) 

Here polynomial M(x,r) is (as proved by K.F.Gauss) for all odd prime r irreducible. The aim is to find his roots (using periods), and by that to solve the binomial equation (congruence).

 G(2,3)= R(2,3,7)
  0              1
  1  2  6        x   x2  x4
  3  6  5        x3  x6  x5
  7              M(x,r)

For r=n^k forms exponents of powers x^u   G(n,k) = R(n,k,r).

For n=2, k=3 is r = 2³−1 = 7:

Periods

We call Gauss periods the expressions of the form s=∑x^u, where u are instances of one particular class of the R-system. Each period is charakterized by g-number of class:    s_i/e = ∑x ^{g∙nj mod r} , where j=0..k−1.

Period is nontrivial if it has more than one member, i.e. when the order of the system is greater than 1.

For labeling of individual sums we will use fraction i/e, where e indicates the number of periods pertaining to that system, i ordinal number of the period. Letter e marks number of Euler's classes (see G-systems). In simple R-systems (rεP) is e = v= (r−1)/k, where v is number of self classes (see G-system/Nesting).

For r = 5, there are two (non-trivial) options for build of periods.

 R(2,4,5)
    0              1
    1  2  4  3     x + x² + x4 + x³ = s0/1
    5              M(x,5)


 R(4,2,5)
    0          1
    1  4       x  + x4  =  s0/2
    2  3       x² +  x³  =  s1/2
    5          M(x,5)

Relations of sums

In the given system we will denote periods as g_i = s_i/e, expressions are bound by certain relations.
E.g.in R(4,2,5):

    0           1
    1  4        x  + x4 = s0/2 = g0
    2  3        x² + x³ = s1/2 = g1
    5           M(x,5)

Because: g₀²  =(x + x⁴)² = x²+2x⁵+x⁸ ≡ x²+2+x³ = g₀+2 (mod M(x,5)) g₁²  =(x²+ x³)² = x⁴+2x⁵+x⁶ ≡ x⁴+2+x = g₁+2 (mod M(x,5)) g₀∙g₁=(x+ x⁴)(x²+ x³)= x³+x⁴+x⁶+x⁷ ≡ x³+x⁴+x+x²=g₀+g₁(mod M(x,5))

it holds:

·   g₀² ≡ g₀+2 resp. g₁² ≡ g₁+2 (mod M(x,5))

·   g₀∙g₁ ≡ g₀+g₁ (mod M(x,5))

Sum of all periods

Sum of number 1 and of all periods g_i form a geometric progression x^u with sum:   1+∑g_i = ∑x^u = (x^r−1)/(x−1) = M(x,r)

Therefore:

 s_G = ∑g_i ≡ −1 (mod M(x,r)) 

E.g.v R(4,2,5) is g₀+g₁ = x+x²+x³+x⁴ ≡ −1 (mod M(x,5)).

Product of the members of periods

Instances consists of exponents of periods members, one period corresponds to one class of R-system R(n,k,r). Because the sum of instances of any kind is always a multiple of r-1, analogous relation applies for the products of the members of periods:

 p_g = ∏ x^u_j ≡ −1 (mod M(x,r)) 

E.g. in R(4,2,5) is x ∙ x⁴ ≡ x² ∙ x³ ≡ 1 (mod M(x,5)).

Disintegration of congruence

If number is n−1 power of number 2, solution of equation xⁿ = 1 decays only to quadratic equations. Trigonometric functions for respective angles is then possible write just using square roots.
E.g. Solution of congruence x¹⁷−1 ≡ 0 (mod 103) depends on E=φ(17)=16=2⁴. It is therefore sufficient to solve the four congruences of the second degree.

Gauss' periods

Gauss' polygons

Regular r-gon is easy to construct by a ruler and compass for r=2^j (square, octagon,...), r=3 (triangle) and r=5 (pentagon) and also for the combinations: r=3∙2^j, r=5∙2^j and r=15∙2^j, jεN₀. Procedures were already known at the time of Euclid. Gauss noticed (y.1796), it is also possible to construct a 17-square (φ(17)=2⁴), respectively each p-gon for Fermat's primes p=2^(2t)+1 (see F-systems). He proved that the possibility of construction depends on prime factorization of number E=φ(n), ie. E=p−1 for pεP (e.g. φ(3)=2¹ and φ(5)=2²).

From combinations (of products) of numbers n=2^j,3,5,17,257,65537,... these values r [Gauss I] arise:   r =2,3,4,5,6,8,10,12,15,16,17,20,24,30,32,34,40,48,51,60, 64,68,80, 85,96,102,120,128,136,160,170,192,204,240,255,256, 257,272,..

Products of odd Fermat numbers makes sequence: 3,5,15,17,51,85,255,257,... (see Binary systems)

Elements that arise by Euclidean constructions (with a ruler and compass) ie. the coordinates of points, directives of lines, the coefficients in the equations of circles .. belong to the field, which originates from the field of coordinates by adding uniquely defined square roots (see Expanding fields).

Pentagon

In the system R(4,2,5) it holds:    g₀∙g₁ ≡ g₀+g₁  ≡ −1 (mod M(x,5)),      g₁    ≡ −g₀−1 (mod M(x,5))    g₀∙g₁ ≡ g₀∙(−g₀−1) ≡ −1 (mod M(x,5))  

 g₀²+g₀−1 ≡ 0 (mod M(x,5)) 

The solution of the quadratic equation g²+g−1=0 is:

·g₀ = (−1+√5)/2

·g₁ = (−1−√5)/2

At this point, we know the values of x + x⁴ = g₀ and x² + x³ = g₁. We will use the relationship for the product of members of periods (see above). to exclusion of x from the expression x + x⁴ = g₀.    x ∙ x⁴ ≡ x² ∙ x³ ≡ 1 (mod M(x,5))    x + x⁴ = g₀ = (−1+√5)/2  =>  x⁴ = g₀−x       x ∙ x⁴ = 1  =>  x(g₀−x) = 1

 x² − g₀x + 1 = 0 

Let us substitute g₀ = (−1+√5)/2 into solution x=x₁ of quadratic equation x² − g₀x + 1 = 0.    x₁ = (g₀+√(g₀²−4))/2   x₂ = (g₀−√(g₀²−4))/2    x = (−1+√5)/4 + i∙√2∙√(5+√5)/4

Heptagon

According to module (mod M(x,7)):    g₀+g₁  ≡  −1  g₀∙g₁  ≡ g₀+g₁+3  =2

From solution of the quadratic equation g²+g+2=0:

·   g₀ = (−1+i∙√7)/2

·   g₁ = (−1−i∙√7)/2 R(6,2,7)     0  1     1  6     x + x⁶  =  g₀     2  5     x² + x⁵  =  g₁     3  4     x³ + x⁴  =  g₂     7  M(x,7)

Relations between roots

According to module M(x,7) it holds e.g.:

·   g₀+g₁+g₂ ≡ −1

·   g₀g₁g₂ ≡ 1, (g₀g₁g₂)² ≡ (g₀+g₁)(g₁+g₂)(g₀+g₂)

·   g₀² ≡ g₁+2, g₁² ≡ g₂+2, g₂² ≡ g₀+2,

·   g₀g₁ ≡ g₀+g₂, g₁g₂ ≡ g₀+g₁, g₀g₂ ≡ g₁+g₂, i.e.g₂ ≡ g₀(g₁−1),...

·   g₀g₁² + g₁g₂² +g₂g₀² ≡ −4 ...

Hence:

·   g₀g₁g₂ ≡ 1   =>   g₀ ≡ 1/(g₁g₂) ≡ 1/(g₀+g₁)

      =>   g₀²+g₀g₁ ≡ 1   =>   g₁ ≡ (1−g₀²)/g₀

·   g₀+g₁+g₂ ≡ −1 => g₀+g₁+g₀(g₁−1) ≡−1 => g₁ ≡ −1/(1+g₀)

So (1−g₀²)/g₀ ≡ −1/(1+g₀) i.e.:

 g₀³+g₀²−2g₀−1 ≡ 0 

Tridecagon

In the case of congruence x¹³−1 ≡ 0 (mod 53) is E=φ(13)=12=2² 3¹. Solving must be converted to 3 congruences: two of second and one of third degree.
After quadratic congruences s_0/2=g₀,s_1/2=g₁ (see above) further follow:

     R(5,4,13), e= (r−1)/k=12/4=3:

        1
        x  + x5  + x12 + x8  =  s0/3
        x2 + x10 + x11 + x3  =  s1/3
        x4 + x7  + x9  + x6  =  s2/3
        M(x,13)

     R(3,3,13), e= (r−1)/k=12/3=4:

        1
        x   +  x3  +  x9  =  s0/4
        x2  +  x6  +  x5  =  s1/4
        x4  +  x12 +  x10 =  s2/4
        x7  +  x8  +  x11 =  s3/4
        M(x,13)

Composite R-systems

In composite R-systems we can build periods only for exponents u relatively prime to r, (u,r) = 1. E.g. G(2,4):

                (1)
                x   +  x² + x4 ²+   x8    s0/2 
              x³ + x6  +  x12 +  x9 
              x5 + x10
              x7 + x14 +  x13 +  x11 s1/2
                M(x,15)

Number of periods is e=φ(r)/k.

Regular prime

Attribute 'regular' receives prime p if it does not divide order of the body obtained by adding p-th (p = r-1) root of unit. To rational numbers (for more see Algebraic equations / Extension fields).

For r= 5

α = (4)√1 =  = √−1 = i :    α = i, α² = −1,   α³ = −α, α⁴ = +1

 │ 1  x   x²  x³ │
 ┼───────────────┼──────────────────────────────
 │ 1             │ R(1,1,5)  σ+= 1+2+3+4= 10
 │ 2             │   σ−= 1−2+3−4= −2
 │ 3             │ 
 │ 4             │   
 ┼───────────────┼──────────────────────────────
 │ 1      4      │ R(4,2,5)  σ+= 3−7i²= 10
 │ 2      3      │ 
 ┼───────────────┼──────────────────────────────
 │ 1  2   4   3  │ R(2,4,5)  σ+= 1+2i−4−3i= −3−i
 │ 1  3   4   2  │ R(3,4,5)  σ+= 1+3i−4−2i= −3+i
 ┼───────────────┼──────────────────────────────

Přitom (−3−i)(−3−i) = 10.

For r= 7

α = (6)√1 = (3)√−1 = (1+i√3)/2 :     α = (1+i√3)/2,  α² = (−1+i√3)/2, 

α³ = −1,  α⁴ = −α,  α⁵ = −α²,  α⁶ = 1

│ 1  x  x² x3  x4x5 │
┼───────────────────────┼─────────────────────────
│ 1                     │ R(1,1,7)  σ+= 1+..+6= 21
│ ..                    │   σ−= 1−..−6= −3
│ 6                     │  
┼───────────────────────┼─────────────────────────
│ 1   6                 │ R(6,2,7)  σ+=  7−14= −7
│ 2   5                 │   σ−= 10−11= −1
│ 4   3                 │
┼───────────────────────┼─────────────────────────
│ 1     2       4       │ R(2,3,7)  σ+= (−9−i∙√3)/2
│ 3     6       5       │
┼───────────────────────┼─────────────────────────
│ 1     4       2       │ R(4,3,7)  σ+= (−9+i∙√3)/2
│ 3     5       6       │
┼───────────────────────┼─────────────────────────
│ 1  3  2   6   4  5    │ R(3,6,7)  σ+= −4−2i∙√3
│ 1  5  4   6   2  3    │ R(5,6,7)  σ+= −4+2i∙√3
┼───────────────────────┼───────────────────────── 

Přitom:  ((−9−i∙√3)/2)((−9+i∙√3)/2) = 21  (−4−2i∙√3)(−4+2i∙√3)   = 28

Quadratic law of reciprocity

Our current knowledge can facilitate the search for residues of the numbers according to a certain module. In this chapter, we look briefly to the (classic but difficult) inverse problem. We will seek all modules that give one given residue.

Number 2 as quadratic residue

Number 2 is quadratic residue, when we find number u = a² mod r = 2 of system R(n,k,r) in the first row.

    r= 7:
    0
    1   2   4
    3   6   5
    7

    r= 17:
    0
    1  2   4   8  16  15  13   9
    3  6  12   7  14  11   5  10
    17 

    r= 23:
    0
    1   2   4   8  16   9  18  13   3   6  12
    5  10  20  17  11  22  21  19  15   7  14
    23

    r= 31:
    0
    1  7  18  2  14  5  4  28  10  8  25  20  16  19  9
    3 21  23  6  11 15 12  22  30 24  13  29  17  26 27
    31 

 According to Euler's kriterion has to be Q(2,r)=2^κ(r) mod r ≡ 1 (mod r), what applies to the following modules r:

    r   κ(r)    a
    ──────────────
    7     3     3
    17     8     6
    23    11     5
    31    15     8
    41    20    17
    47    23     7 

    r    κ(r)   a
    ──────────────
    71    35    12
    73    36    32
    79    39     9
    89    44    25
    97    48    14 

Value a=√(2) (mod r). E.g. √(2) (mod 7) = 3 because 3² ≡ 2 (mod 7). Number 2 is a quadratic non-residue for other unoccupied primes r,

ie for r = 2,3,5,11,13,19,29,37,43,53,59,61,67,83 resp. κ(r) = 1,1,2,5,6,9,14, 18,21,26,29,30,33,41.

    r= 5:
    0
    1   4
    2   3
    5

    r= 11:
    0
    1   3   9   5   4
    2   6   7  10   8
    11 

    r= 13:
    0
    1   4   3  12   9  10
    2   8   6  11   5   7
    13

    r= 19:
    0
    1   4  16   7   9  17  11   6   5
    2   8  13  14  18  15   3  12  10
    19 

              0    1   4  16   6  24   9   7  28  25  13  23   5  20  22    2   8   3  12  19  18  14  27  21  26  17  10  11  15   29 

Gauss' rule

To determine whether a number Z is a quadratic residue (mod r), the values of residues z(k) = k ∙ Z mod r, for k = 1..κ(r) are needed. Number Z is quadratic residue only in the case, where the number of residues larger than r/2 among the z(k) is even.

For r=17, Z= 7 is κ(r)=8, r/2 = 8.5. The first 8 residues are:

   k:     1  2  3  4  5  6  7  8
   k∙Z:   7 14 21 28 35 42 49 56
  ─────────────────────────────── 
  z(k):   7 14  4 11  1  8 15  5 

Because the number of residues greater than 8.5 is odd (there are three numbers: 11,14 a 15) number 7 is non-residue according to module 17.

For r=19 and r=23 we verify, whether Z=2 is quadratic residue.

· Among 9 residues (2,4,6,8,10,12,14,16,18) 5 numbers are greater than 9.5. Number 2 is quadratic non-residue (mod 19).

· For r=23 among 11 residues (2,4,6,8,10,12,14,16,18,20,22), 6 numbers are greater than 11.5. Number 2 is quadratic residue (mod 23).

For Z=2 is z(k) = k∙Z. The observed number of numbers therefore depends only on the form of number r respectively κ(r) (κ(19) = 9, κ(23) = 11).
Number 2 is quadratic residue (mod r) when κ(r) is genuine odd number (ie. number of the form 4s+1).

Distribution of residues and non-residues

Genuine odd numbers

In quadratic systems R(n,k,r) where r is an genuine odd number, is number -1 always on the second row. Therefore the residue contrasting to the given residue has an opposite "polarity": if u is a quadratic residue −u = r−u is quadratic non-residue.

E.g.    v R(2,3,7) number 2 is quadratic residue and number −2 is nonresidue,

·    v R(3,5,11) number −2 is quadratic residue and number 2 is nonresidue,

·    v R(4,9,19) number −2 is quadratic residue and number 2 is nonresidue.

  R(2,3,7)     R(3,5,11)        R(4,9,19)
    0           0                0
    1  2 −3     1  3 −2  5  4    1 4 −3  7  9 −2 −8  6  5
    3 −1 −2     2 −5 −4 −1 −3    2 8 −6 −5 −1 −4  3 −7 −9   
    0           0                0

Non-genuine odd numbers

In quadratic systems R(n,k,r), where r is an non-genuine odd number, is always number -1 in the first row. Therefore, the mutually contrasting residues occur within the same class.

E.g.

·    in R(4,2,5) are numbers 1,−1 quadratic residues,

·    in R(4,6,13) are numbers 1,−1, 3,−3 and 4,−4 quadratic residues.

   0           0              
   1  −1       1  4  3 −1 −4 −3  
   2  −2       2 −5  6 −2  5 −6
   0           0 

Modalities of primes modules

We will look for prime modules r (resp. their medians κ(r)), for that is u the quadratic residue, i.e. there exists such number s, that s²≡u (mod r).
When we write a sequence of numbers κ (r) on a circle, we find that there are certain periods of repetition.

Suppose first division of the circle to 2∙u points. When u is squared (u = 4,9,16, ..) values of r cover all primes. In other cases, for the coverage of numbers κ(r) only certain points on the circle are sufficient.

Ať pokračujeme v sequences numbers κ(r) jakkoliv daleko, nikdy (až na případ kdy u=a²) jejich obrazy nepokryjí celou kružnici, ale jen určité vybrané body. In music theory term modality became known for selection of such points (see the musical structures).

For u=2..20 we get modalities:

 u  κ(r)                              κ(r) mod 2u
─────────────────────────────────────────────────────────────
 2: 3,8,11,15,20,23,35,36,39,44,48,.. 0,3
 3: 5,6,11,18,23,29,30,35,36,41,48,.. 0,5
 4: 1,2,3,5,6,8,9,11,14,15,18,20,21,. ────
 5: 5,9,14,15,20,29,30,35,39,44,50,.. 0,4,5,9
 6: 2,9,11,14,21,23,26,33,35,36,48,.. 0,2,9,11
 7: 1,9,14,15,18,23,26,29,41,51,54,.. 0,1,4,9,12,13
 8: 3,8,11,15,20,23,35,36,39,44,48,.. 0,3,4,7,8,11,12,15
 9: 2,3,5,6,8,9,11,14,15,18,20,21,... ────
10: 1,6,15,18,20,21,26,33,35,39,41,.. 0,1,4,6,13,15,18,19
11: 2,3,9,18,21,26,39,41,44,48,53,... 0,2,3,4,9,12,17,18,19,21
12: 5,6,11,18,23,29,30,35,36,41,48,.. 0,5,6,11,12,17,18,23
13: 1,8,11,14,21,26,30,39,50,51,53,.. 0,1,4,8,11,12,13,14,17,21,24,25
14: 2,5,6,15,21,23,30,33,50,51,53,... 0,2,4,5,6,12,15,21,22,23,25,27
15: 3,5,8,21,26,29,30,33,35,51,54,... 0,3,5,8,21,24,26,29
16: 1,2,3,5,6,8,9,11,14,15,18,20,.... ──── 

·    For prime u has the modality u−1 values.

·    Periods can be reduced to half for non-genuine odd u (ie. u of the form 4s+1), eg.:

 u  κ(r) mod 2u                                  κ(r) mod u
──────────────────────────────────────────────────────────────────
 5: 0,4,5,9                                       0,4
13: 0,1,4,8,11,12,13,14,17,21,24,25               0,1,4,8,11,12
17: 0,4,6,7,9,10,12,16,17,21,23,24,26,27,29,33    0,4,6,7,9,10,12,16

Symmetry of sequences

All the sequences of the preceding paragraph are symmetrical, the axis of symmetry passes between the points 0 and 2u -1. The following applies:

 ∑a ≡ 0 (mod 2u−1) 

where a represent particular numbers of the sequence (for a given u). E.g. 0+1+4+9+12+13 ≡ 0 (mod 13).

Let us rewrite all the numbers relative to the point, through which the axis of symmetry goes, i.e. the point -1/2.

 u  κ(r) mod 2u          To axis of symetry                 κ(r) mod u   To axis of symetry
──────────────────────────────────────────────────────────────────────────────────────────
 2: 0,3                  1/2,−1/2                                −
 3: 0,5                  1/2,−1/2                                −
 4: ────                                                         −  
 5: 0,4,5,9              1/2,9/2,−9/2,−1/2                      0,4         1/2,−1/2
 6: 0,2,9,11             1/2,5/2,−5/2,−1/2                       −
 7: 0,1,4,9,12,13        1/2,3/2,9/2,−9/2,−3/2,−1/2              −
 8: 0,3,4,7,8,11,12,15   1/2,7/2,9/2,15/2,−15/2,−9/2,−7/2,−1/2   −
 9: ────                                                         −
10: 0,1,4,6,13,15,18,19  1/2,3/2,9/2,13/2,−13/2,−9/2,−3/2,−1/2   − 

Relations for u=2,3,5

For u=2 and u=3 (and odd r) is:

    κ(r) ≡ −1/2 ± 1/2 (mod 2u)
    1/ κ(r) ≡  0 ───>  (r−1)/2 ≡ 0 (mod 2u) 
    2/ κ(r) ≡ −1 ───>  (r+1)/2 ≡ 0 (mod 2u) 
    (r−1)(r+1)/4 ≡ 0 (mod 2u)   => r²−1 ≡ 0 (mod 2²∙2u) 

Case u = 5 (in view of the shape 4s + 1) can be converted to the same equations with half module (mod u).

    κ(r) ≡ −1/2 ± 1/2 (mod 10)  κ(r) ≡ −1/2 ± 9/2 (mod 10)
    κ(r) ≡ −1/2 ± 1/2 (mod 5)   => r²−1 ≡ 0 (mod 2²∙u). 

Therefore u is quadratic residue:

    u=2: když r²−1 is divisible by 16, pak (r²−1)/8 is even and r has form 8s±1.
    u=3: když r²−1 is divisible by 24, pak (r²−1)/12 is even and r = 12s±1.
    u=5: když r²−1 is divisible by 20, pak (r²−1)/10 is even and r = 10s±1. 

Relations for u>5

Other cases can not be reduced and therefore are more complex.

For u=6:

    κ(r) ≡ −1/2 ± 1/2 (mod 12) or  κ(r) ≡ −1/2 ± 5/2 (mod 12)
        => (r²−1)(r²−25) ≡ 0 (mod 24∙2u). 

Equation is satisfied by numbers t of form 24s±1 a 24s±5.

For u=7:

    κ(r)≡ −1/2 ± 1/2 (mod 14) or  κ(r) ≡ −1/2 ± 3/2 (mod 14) or
    κ(r)≡ −1/2 ± 9/2 (mod 14) => (r²−1)(r²−9)(r²−81)≡ 0 (mod 28∙2u). 

Symmetry of primes

Let us break prime numbers (in the range 1-50) down into lines as follows.

·The first number in each line will be pεP.

· Let as write after the colon just such numbers qεP, that q mod p is a quadratic residue by module p:

·If q = p, we will write q in brackets.

    2: 3,5,7,11,13,17,19,23,29,31,37,41,43,47
    3: (3),7,13,19,31,37,43
    5: (5),11,19,29,31,41
    7: 2,(7),11,23,29,37,43
   11: 3,5,(11),23,31,37,47
   13: 3,(13),17,23,29,43
   17: 2,13,(17),19,43,47
   19: 5,7,11,17,(19),23,43,47
   23: 2,3,13,(23),29,31,41,47
   29: 5,7,13,23,(29)
   31: 2,5,7,19,(31),41,47
   37: 3,7,11,(37) 

The two numbers, of which at least one is not a genuine odd (e.g. 17 and 19) form a symmetrical image in the following sense:
number 17 is in the 19-th row and the number 19 again in the 17-th row.

Quadratic law of reciprocity

The answer to the question, in what case is number p a quadratic residue according to q. (p ≡ a² mod q)
and also number q quadratic residue according to p (q ≡ b² mod p) is called quadratic law of reciprocity:

 Q(p,q) ∙ Q(q,p) = (−1)^{κ(p)∙κ(q)} 

Relationship was discovered by Legendre, special cases were described before him by Euler and Lagrange. Gauss in the theory of biquadratic residues generalized relationship for complex numbers.

For genuine odd numbers it holds:

·   Q(−1,p) = −1 a Q(2,p) = −Q(−2,p) (pεP)

·   Q(p,q) = −Q(q,p),  ie. the relationship of reciprocity is anti-symmetrical (p,qεP, p,q>2)

For non-genuine odd numbers it holds:

·   Q(−1,p) = 1 a Q(2,p) = Q(−2,p) (pεP)

·    Q(p,q) = Q(q,p),  ie. the relationship of reciprocity is symmetrical (p,qεP, p,q>2)

Proof of the law of reciprocity

Quadratic systems

Quadratic systems R(p,k,r), where k = κ(r) with the number of classes e=(r−1)/k=2 Divide into two groups according to the value r (genuine odd and non-genuine odd).

We will be interested in the product t_G =g₀g₁ in systems with prime number r.

Genuine odd r :

     R(2,3,7)
       1
       x + x2 + x4   =  g0
       x3 + x6 + x5 =  g1
       M(x,7)
       r=7        
                                       x x2 x4
                                 ───┼──────────
    x3 │  x4 x5 1
    x6 │  1    x    x3  
    x5 │  x6 1 x2

     R(3,5,11)
       1
       x + x3 + x9 + x5 + x4 =  g0
       x2 + x6 + x7 +  x10 + x8 =  g1       
       M(x,11)
       r=11
      x  x3  x9 x5 x4
             ───┼────────────────
  x2 │  x3 x5 1 x7 x6
  x6 │  x7 x9 x4 1  x10
  x7 │  x8 x10 x5 x 1
  x10│  1 x2 x8 x4 x3
  x8 │  x9 1   x6 x2 x

Non-genuine odd r :

    R(4,2,5)
        1
        x + x4 =   s0/2 = g0
        x2 + x3 =   s1/2 = g1
        M(x,5)
    r=5
     x   x4
  ───┼───────────
  x2 │  x3  x
  x3 │  x4  x2  

    R(4,6,13)
    1
    x + x4  + x3 + x12 + x9 + x10 = g0
    x2 + x8  + x6 + x11 + x5 + x7 =  g1
    M(x,13)
    r=13
                                x  x4 x3   x12 x9 x10
     ──┼─────────────────────
    x2 │ x3  x6  x5 x  x11  x12
    x8 │ x9  x12 x11 x7 x4  x5 
    x6 │ x7  x10 x9  x5 x2  x3 
    x11│ x12  x2 x   x10 x7 x8
    x5 │ x6  x9  x8  x4  x  x2
    x7 │ x8  x11 x10 x19 x3 x4

Evaluation of the product

Product t_G =g₀g₁ contains in quadratic systems R(n,κ(r),r) always several (say C) sums (with r-1 members):  s_G = x+x²+... +x^r−1  and several (say J) units, the following applies:

·    J= κ(r), when r is genuine odd

·    J= 0, when r is non-genuine odd

All numbers cover a square of edge κ(r), so (r−1)∙c + J = κ²(r), ie. (after substitution κ(r)=(r−1)/2):

·   c=(r−3)/4, when r is genuine odd

·   c=(r−1)/4, when r is non-genuine odd

Because s_G = x+x²+... +x^r−1 ≡ −1 (mod M(x,r))  (see Sum of all periods),

is t_G = g₀g₁ = J − c, i.e. (after substitution for J and c):

 t_G=g₀g₁ ≡ (1±r)/4 (mod M(x,r)) 

Roots of the congruence

Let us denote t=(1±r)/4, so ±r=4t−1. Therefore r has form r=4s−1 (for s=t) or r=4s+1 (for s=−t). From relations:    s_G=g₀+g₁ ≡ −1 (mod M(x,r))    t_G=g₀g₁  ≡  t (mod M(x,r))

quadratic equation follows for roots of the congruence:

·    for r=4s−1, t= s: x²+x+s=0,

·    for r=4s+1, t=−s: x²+x−s=0.

(? degree p and order κ(r) are prime numbers pεP (p>2), rεP ?)

Proper proof

We will attempt to understand the Gauss proof of the law of reciprocity (3.Gauss evidence), see [Gauss II, General discussion on equations $ 366].

The aim is to prove that if ±p is quadratic residue according to r, then also r is a quadratic residue by p.

When ±p is the degree of R(p,k,r) and it lay in the first of two lines of R-system, it means that the ±p is a quadratic residue according to module rεP.

In R(3,5,11) +3 is quadratic residue mod 11; in R(4,10,13) ±3 is quadratic residue mod 13:

 R(3,5,11)            R(4,10,13)
  0                    0                    0
  1 3 9  5 4           1 10 9 12 3  4       1 −3 −4 −1 3  4 
  2 6 7 10 8           2  7 5 11 6  8       2 −6  5 −2 6 −5
 11                   13                    0

When ±p is quadratic residue by r=4s±1, so it holds:

·    for r=4s+1: x²+x−s=0,

·    for r=4s−1: x²+x+s=0.

 (see the Gauss periods / Quadratic Systems), ie. x²+x±s ≡ 0 (mod p)

Therefore 4x²+4x±4s ≡ 0 (mod p), (2x+1)² ± r (mod p), i.e. 2k|(p−1).

In R (p, k, r) is always r^k ≡ 1 (mod r). In the case where 2k | (p-1), i.e. 2q = (p-1) for vεN is is r^(p−1)/2v ≡ 1 (mod r). When a number is a congruent with the number one, also each of his power is congruent with the number one, so also r^(p−1)/2 =r^κ(p) ≡ 1 (mod r) (see Euler criterion). Thus r is quadratic residue by p.