You're reading an English translation of
the original Czech page.

Diofantos z Alexandrie [dyofantios], around y.250 AD., Greek mathematician, one of the greatest mathematicians Greco-Roman antiquity. He was interested in arithmetic, especially in solutions of indeterminate (Diophantine) equations. He sought the solutions generally in the field rational numbers. He initiated the development of the theory of numbers. In the Diofanta work - there are germs of algebraic symbols - abbreviations for writing negative numbers, inverted values, squares .. |

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:

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

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

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_{1}∙x + a_{0} ≡ 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].

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).

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]

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 x^{4}mod 7 has (3,6) = 3 solutions has (4,6) = 2 solutions ─────────────────────────── ─────────────────────────── x³ 0 1 8 27 64 125 216 x^{4}0 1 16 81 256 625 1296 x³ mod 7 0 1 1 6 1 6 6 x^{4}mod 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

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).

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^{7}−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.

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)

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^{31}−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^{31}−1 ≡ 0 (mod 311) is
E=φ(31)=30=2^{1}∙3^{1}∙5^{1}.
Solutions must be converted to 3 congruences:
of the second, third and fifth degree.

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^{ }+ x^{6 }+ x^{5 }+ x^{30}+ x^{25}+ x^{26}= s(5,0) x^{2}+ x^{12}+ x^{10}+ x^{29}+ x^{19}+ x^{21}= s(5,1) x^{3}+ x^{18}+ x^{15}+ x^{28}+ x^{13}+ x^{16}= s(5,2) x^{7}+ x^{11}+ x^{4 }+ x^{24}+ x^{20}+ x^{27}= s(5,3) x^{8}+ x^{17}+ x^{9 }+ x^{23}+ x^{14}+ x^{22}= s(5,4) x^{31}−1

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.

E.g. for r=9 is the highest possible order k=6.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.

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

Otherwise is:

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^{ }x^{2}−1 x^{4}−1 x^{8}−1 x^{3}−1 x^{6}−1 x^{12}−1 x^{9}−1 (mod p) x^{5}−1 x^{10}−1 x^{7}−1 x^{14}−1 x^{13}−1 x^{11}−1 x^{15}−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^{ }x^{2}−1 x^{4}−1 x^{8}−1 x^{7}−1 x^{14}−1 x^{13}−1 x^{11}−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.

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

Congruence Cycle Solution (1) x^{6}−1 ≡ 0 (mod 5) (6,5−1) = 2 1,4 (2) x^{6}−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_{1} − 5v∙x_{2},
where x_{1},x_{2}
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_{1}−20∙x_{2}.
Hence xε{1,4,6,9,11,16,19,24,26,29,31,34}.

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 ─────────────────────────────────────────────────── x^{2}1 1 1 16 11 16 11 11 16 11 16 x^{3}1 1 29 29 34 34 6 6 x^{4}11 16 16 11 16 11 x^{5}9 4 24 19 31 26 x^{6}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

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 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).

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^{15}−1=0 shares the roots with x^{5}−1=0 and
x³−1=0 because x^{15}−1 is divisible by x^{5}−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.

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^{4}+
x^{5}+x^{6} = (x^{7}−1)/(x−1) = M(x,7).

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^{8} ≡ x³ (mod M(x,5)), for x=3: 6561 ≡ 27 (mod 242).

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

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^{ }x^{2}x^{4}3 6 5 x^{3}x^{6}x^{5}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:

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² + x^{4}+ x³ = s0/1 5 M(x,5) R(4,2,5) 0 1 1 4 x + x^{4}= s_{0/2}2 3 x² + x³ = s_{1/2}5 M(x,5)

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 + x^{4}= s_{0/2}= g_{0}2 3 x² + x³ = s_{1/2}= g_{1}5 M(x,5)

Because:
g_{0}² =(x + x^{4})² = x²+2x^{5}+x^{8}
≡ x²+2+x³ = g_{0}+2 (mod M(x,5))
g_{1}² =(x²+ x³)² = x^{4}+2x^{5}+x^{6}
≡ x^{4}+2+x = g_{1}+2 (mod M(x,5))
g_{0}∙g_{1}=(x+ x^{4})(x²+ x³)= x³+x^{4}+x^{6}+x^{7}
≡ x³+x^{4}+x+x²=g_{0}+g_{1}(mod M(x,5))

it holds:

·
g_{0}² ≡ g_{0}+2 resp.
g_{1}² ≡ g_{1}+2 (mod M(x,5))

·
g_{0}∙g_{1} ≡ g_{0}+g_{1} (mod
M(x,5))

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:

E.g.v R(4,2,5) is g_{0}+g_{1} =
x+x²+x³+x^{4} ≡ −1 (mod M(x,5)).

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:

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

If number is n−1 power of number 2, solution of equation x^{n} = 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^{17}−1 ≡ 0 (mod 103) depends on
E=φ(17)=16=2^{4}.
It is therefore sufficient to solve the four congruences of the second degree.

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_{0}.
Procedures were already known at the time of Euclid.
Gauss noticed (y.1796), it is also possible to construct a 17-square (φ(17)=2^{4}),
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^{1} 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).

In the system R(4,2,5) it holds:
g_{0}∙g_{1} ≡
g_{0}+g_{1} ≡ −1 (mod M(x,5)),
g_{1} _{ }≡
−g_{0}−1 (mod M(x,5))
g_{0}∙g_{1} ≡
g_{0}∙(−g_{0}−1) ≡ −1 (mod M(x,5))

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

·g_{0} = (−1+√5)/2

·g_{1} = (−1−√5)/2

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

Let us substitute g_{0} = (−1+√5)/2 into
solution x=x_{1} of quadratic equation x² − g_{0}x + 1 = 0.
x_{1} =
(g_{0}+√(g_{0}²−4))/2
x_{2} = (g_{0}−√(g_{0}²−4))/2
x = (−1+√5)/4 + i∙√2∙√(5+√5)/4

According to module (mod M(x,7)):
g_{0}+g_{1} ≡
−1 g_{0}∙g_{1} ≡
g_{0}+g_{1}+3 =2

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

·
g_{0} = (−1+i∙√7)/2

·
g_{1} = (−1−i∙√7)/2
R(6,2,7)
0 1
1 6 x +
x^{6} = g_{0}
2 5 x² +
x^{5} = g_{1}
3 4 x³ +
x^{4} = g_{2}
7 M(x,7)

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

·
g_{0}+g_{1}+g_{2} ≡ −1

·
g_{0}g_{1}g_{2} ≡ 1,
(g_{0}g_{1}g_{2})² ≡
(g_{0}+g_{1})(g_{1}+g_{2})(g_{0}+g_{2})

·
g_{0}² ≡ g_{1}+2,
g_{1}² ≡ g_{2}+2, g_{2}² ≡
g_{0}+2,

·
g_{0}g_{1} ≡ g_{0}+g_{2},
g_{1}g_{2} ≡ g_{0}+g_{1},
g_{0}g_{2} ≡ g_{1}+g_{2},
i.e.g_{2} ≡ g_{0}(g_{1}−1),...

·
g_{0}g_{1}² +
g_{1}g_{2}²
+g_{2}g_{0}² ≡ −4 ...

Hence:

·
g_{0}g_{1}g_{2} ≡ 1
=> g_{0} ≡ 1/(g_{1}g_{2}) ≡
1/(g_{0}+g_{1})

=>
g_{0}²+g_{0}g_{1} ≡ 1
=> g_{1} ≡
(1−g_{0}²)/g_{0}

·
g_{0}+g_{1}+g_{2} ≡ −1 =>
g_{0}+g_{1}+g_{0}(g_{1}−1) ≡−1 =>
g_{1} ≡ −1/(1+g_{0})

So (1−g_{0}²)/g_{0} ≡
−1/(1+g_{0}) i.e.:

In the case of congruence x^{13}−1 ≡ 0 (mod 53) is E=φ(13)=12=2² 3^{1}.
Solving must be converted to 3 congruences: two of second and one of third degree.

After quadratic congruences s_{0/2}=g_{0},s_{1/2}=g_{1}
(see above) further follow:

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

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² + x^{4}²+ x^{8}s_{0/2}x³ + x^{6 }+ x^{12}+ x&sup9; x^{5}+ x^{10}x^{7}+ x^{14}+ x^{13}+ x^{11}s_{1/2}M(x,15)

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

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).

α = (4)√1 = = √−1 = i :
α = i, α² = −1, α³ = −α, α^{4} = +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.

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

α³ = −1, α^{4} = −α, α^{5} =
−α², α^{6} = 1

│ 1 x x² x3 x^{4}x5 │ ┼───────────────────────┼───────────────────────── │ 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

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 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

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).

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

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

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

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 −

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.

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 2^{4}∙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 2^{8}∙2u).

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.

Gauss, Karl Friedrich , 1777-1855,
German mathematician and physicist, called the "Prince of mathematicians"
by his contemporaries. From childhood he was an extraordinary mathematical
talent. He continued on Euler's work, proved fundamental theorem of algebra
and the law of reciprocity (by several independent ways). He was engaged in congruences, complex numbers, convergence of series, interpolation, substitution, solving systems of equations, calculus of variations. Mathematically formulated laws of electromagnetism, participated in the invention of the telegraph; he has also devoted to astronomy and optics. Published only the results he considered mature, and thus he knowingly did not publish eg. his discovery of hyperbolic geometry. Gauss scientific works are brilliant and revealing the ingenious insight of the author. |

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:

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)

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_{0}g_{1}
in systems with prime number r.

Genuine odd r :

R(2,3,7) 1 x + x |
R(3,5,11) 1 x + x |

Non-genuine odd r :

R(4,2,5) 1 x + x |
R(4,6,13) 1 x + x |

Product t_{G} =g_{0}g_{1} 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_{0}g_{1} = J − c, i.e. (after substitution for J and c):

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_{0}+g_{1} ≡ −1 (mod M(x,r))
t_{G}=g_{0}g_{1} ≡ 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 ?)

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.