Kongruence

Od kongruencí k zákonu reciprocity

Základní pojmy

Kongruence čísel

Pokusy o řešení Diofantových neurčitých rovnic inspirovaly zavedení tzv.kongruencí.

Jestliže číslo r dělí rozdíl a−b, pak čísla a,bεZ jsou kongruentní vzhledem k r. Číslo rεN se nazývá modul.
Čísla kongruentní vzhledem k složenému modulu jsou také kongruentní vzhledem k libovolnému děliteli tohoto modulu.

Výraz, který obsahuje dvě kongruentní veličiny ve tvaru rovnice (se symbolem ≡), se nazývá kongruence. Když a≡b (mod r) tak (pro a,b,cεZ) platí:

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

Dělit obě strany kongruence je možné jedině číslem c nesoudělným s modulem, (c,r) = 1:

 a/c ≡ b/c (mod r) 

V případě kdy c|a, c|b, c|r je možné celou kongruenci zkrátit:

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

Řešení kongruencí

Všechny algebraické kongruence s jednou neznámou mohou být převedeny na tvar X≡0, kde X je algebraická funkce proměnné X neobsahující zlomky.
Kongruence a_k∙x^k + a_k−1∙x^k−1 + ... + a₁∙x + a₀ ≡ 0 (mod r) má buď nekonečně mnoho řešení nebo nemá více než k řešení.

Řešení kongruencí se zapisují analogicky jako řešení rovnic. Pro jednoduché lineární kongruence ax ≡ b (mod r): x≡b/a a pro kongruence vyšších stupňů x^k ≡ c (mod r): x≡ √c (mod r) [Gauss,I].

Kongruence podle komplexního modulu

Všechna čísla která zaujímají stejnou polohu vzhledem k čtvercové síti soustavy (0XY) jsou vzájemně kongruentní.
Např. v síti násobků čísla (2+i) leží bod i v levém dolním rohu čtverce {0,2+i,1+3i,−1+2i}. Stejnou polohu zaujímá bod 3 uvnitř čtverce {3−i,5,4+2i,2+i}. Proto i ≡ 3 mod (2+i).

Kongruence polynomů

Polynomy P=a+bx+cx²+dx³+... a P'=a'+b'x+c'x²+d'x³+... se nazývají kongruentní podle modulu r, když koeficienty při stejných stupních x jsou kongruentní (tj. a≡a',b≡b',... mod r). Pro polynomy platí ve většině případů totéž co pro čísla.

Polynom Q je podíl R/P podle daného modulu, jestliže PQ≡R. Všechny polynomy kongruentní s Q se považují v takovém případě za jeden jediný. V některých případech ale podíl může mít několik (nekongruentních) hodnot.[Gauss,II]

Prostá binomická kongruence

Definice

Kongruenci tvaru x^h−1 ≡ 0 (mod p) nazýváme binomická kongruence . Zatímco binomické rovnice x^h−1 = 0 mají vždy h (nebo nekonečně mnoho) řešení, u binomických kongruencí tomu tak být nemusí. Podle Malé Fermatovy věty platí: x^p−1−1 ≡ 0 (mod p) (pro pεP). Cyklus kořenů délky h se u binomických kongruencí skládá s cyklem Malé Fermatovy věty (viz).

Kongruence x^h−1 ≡ 0 (mod p) má vždy (h,p−1)=s kořenů a tyto kořeny odpovídají řešení kongruence x^s−1 ≡ 0 (mod p):

 Kongruence  x³ mod 7               Kongruence  x4mod 7     
  má (3,6) = 3 řešení                  má (4,6) = 2 řešení
───────────────────────────         ───────────────────────────
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  

Cyklus binomické kongruence

Největší společný dělitel exponentu h a čísla p−1 (modulu p sníženého o jedničku) nazveme cyklem kongruence , c=(h, p−1).

Vhodné moduly

Za vhodný modul budeme považovat takové prvočíslo p které nenarušuje cyklus rovnice h. Takovou vlastnost mají čísla p pro která h|(p−1), tj. (h,p−1)=h. Vhodnými moduly jsou tedy prvočísla tvaru t∙h+1 (tεN).
Např. k rovnici x⁷−1=0 je první vhodné prvočíslo p=29, protože čísla 1∙7+1=8, 2∙7+1=15 i 3∙7+1=22 jsou složená.

G-systémy s prvočíselným řádem

V následujícím přehledu jsou vypsány řádky vybraných G-systémů s prvočíselným řádem k i modulem r=n^k−1.

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

Ze součinu výrazů (x−u), kde u jsou jednotlivé instance, dostaneme polynomy kongruentní s výrazem 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) 

Rozklad kongruence

Řešení kongruence x^h−1 ≡ 0 (mod p) závisí na rozkladu čísla E=φ(h) v součin prvočinitelů. Nechť rozklad čísla E je E=∏pi^di. Pak je možné sestavit ∑di kongruencí nižších stupňů, přičemž vždy di kongruencí je stupně pi. Např. uvažujme kongruenci x³¹−1≡0 (mod p). Vhodný modul je prvočíselný tvaru p=b∙r+1 (viz výše). V posloupnosti 32,63,94,125,156,187,218,249,280,311,342,... je prvním takovým vhodným číslem p=311.

Pro kongruenci x³¹−1 ≡ 0 (mod 311) je E=φ(31)=30=2¹∙3¹∙5¹. Řešení je nutné převést na 3 kongruence: druhého, třetího a pátého stupně.

Využití primitivních kořenů

Při sestavování period Gauss využívá primitivních kořenů. Hledejme takové číslo z, jehož mocniny z^h (mod r) projdou (pro h=0,1,2,..,φ(r)) všechna čísla nesoudělná s r, tj. primitivní kořen rovnice z^φ(r) ≡ 1 (mod r). Posloupnost čísel z^h (mod r) pak vepíšeme do tabulky následujícím způsobem. Označíme h=j∙e+i a nadepíšeme řádky tabulky i=0,1,..,(e−1) a sloupce j=0,1,...(k−1). Čísla v takto získaných periodách odpovídají (až na pořadí) instancím 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 

Systém R(6,6,31), e= φ(r)/k=30/6=5, je tvořen následujícími periodami:

    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

Složená binomická kongruence

Zobecnění primitivních kořenů

Primitivní kořeny jsme dosud hledali jen pro prvočíselné moduly r. Nyní bychom chtěli jejich definici rozšířit i na složené moduly. Zde nemůžeme (tak jako u rεP) je vybrat systémy s řádem k= r−1. Takové totiž neexistují. Hledejme proto systémy s nejvyšším možným řádem.

  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

Zdá se, že by původní definici primitivních kořenů mohlo jít zobecnit náhradou řádu k= r−1, řádem k=φ(r). I zde dostanou význam primitivních kořenů (podle modulu r) stupně systémů (v našem příkladě 2 a 5). Počet systémů s daným řádem k je φ(k) = φ(φ(r)).

Systémy s řádem k=φ(r) ale neexistují vždy, např. neexistují pro modul r=8 [viz Univerzální exponent]. Existují jen pro moduly r=2,4,p^e a 2∙p^e, kde pεP a eεNo.

Součin primitivních kořenů

Když modul r má primitivní kořen, tak platí: (Gauss,1801, $78)

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

V opačném případě je:

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

Dělitelnost

Řešení binomické kongruence (pro pεP)   x^r−1 ≡ 0 (mod p)

souvisí s dělitelností výrazu M(x,r).

Výraz x^r−1 je dělitelný x^q−1 tehdy, když q|r.

Přepišme schéma systému G(2,4)=R(2,4,15) tak, že čísla instancí umístíme do exponentů proměnné 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

Výrazy, jejichž exponenty q jsou nesoudělné s r, tj. (q,r)=1, nemohou být soudělné s M(x,r).

Proto M(x,r) není dělitelné žádným z výrazů:

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

Tyto výrazy budeme nazývat primitivní kořeny . Počet primitivních kořenů je určen Eulerovou funkcí: E=φ(r). V systému s řádem k tvoří výrazy e=E/k = φ(r)/k druhů. V našem příkladě E=φ(15)=8, e=φ(15)/4=8/4=2.

Struktura řešení

Mějme složenou binomickou kongruenci x⁶−1 ≡ 0 (mod 35). Platí zároveň:

   Kongruence     Cyklus     Řešení
   (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

Existuje 2∙6 = 12 řešení. Řešení je možné určit např. podle vztahu x= 7u∙x₁ − 5v∙x₂, kde x₁,x₂ jsou různá řešení kongruencí (1)(2) a čísla u,v jsou vybrána tak, aby bylo 7u−5v = 1.

Např.pro u=3, v=4 je 7∙3−5∙4 = 1 a x=21∙x₁−20∙x₂. Odtud xε{1,4,6,9,11,16,19,24,26,29,31,34}.

Řád řešení

Řešení x je řádu d, když x^d ≡ 1 (mod p), pro 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

Vlastní a vnořená řešení

Pro každý řád představuje počet kořenů počet vlastních řešení. Celkový počet řešení (včetně vnořených) získáme podle následujícího schematu:

 Řád Celkem řešení           Vnořená řešení  Vlastní řešení           
───────────────────────────────────────────────────────────
 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

Součin řešení

Součin všech řešení, která vyhovují kongruenci x^r−1 ≡ 0 (mod p) je podle modulu p kongruentní s jedničkou.

V našem příkladě je:  1∙4∙6∙9∙11∙16∙19∙24∙26∙29∙31∙34 = 13776637095936 = 393618202741 ∙ 35 + 1.

Z kořenů můžeme také sestavit skupiny (1), (4,9), (11,16), (19,24), (26,31), (6,29,34), kde uvnitř každé z nich je součin čísel ≡ 1 (podle modulu p).

Rozlišení případů

Když je číslo r složené, nepřísluší všechny kořeny kongruence x^r−1≡0 danému systému R(n,k,r), ale vnořují se z jiných systémů.
Např. rovnice x¹⁵−1=0 sdílí kořeny s x⁵−1=0 a x³−1=0 protože x¹⁵−1 je dělitelné x⁵−1 i x³−1. Proto je možné omezit zkoumání jen případy, kdy r je prvočíslo nebo mocnina prvočísla. Označíme r=t^ν, kde tεP. Pak je E=φ(r)=φ(t^ν)=(t−1)∙t^ν−1 = r∙(t−1)/t.

Mocninné výrazy

Součet mocnin x^u

Instance u systému R(n,k,r) procházejí všechna čísla 0,..,r−1. Mocniny x^u tvoří geometrickou posloupnost se součtem: ∑x^u = (x^r−1)/(x−1) = M(x,r)

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

Zbytky podle modulu M(x,r)

Mocniny x^s (pro sεN) dávají podle modulu x^r−1 zbytky téhož tvaru, tj. např. x^u (uεN, u<s). Přitom platí s ≡ u (mod r):      x^s ≡ x^u (mod x^r−1)  <==> s ≡ u (mod r)

Např. x⁸ ≡ x³ (mod M(x,5)), pro x=3: 6561 ≡ 27 (mod 242).

Protože x^r−1 je násobkem M(x,r), platí také:

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

Přitom polynom M(x,r) je (jak dokázal K.F.Gauss) pro všechna lichá prvočíselná r nerozložitelný. Cílem je najít jeho kořeny (pomocí period) a tím řešit binomickou rovnici (kongruenci).

 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)

Pro r=n^k tvoří exponenty mocnin x^u   G(n,k) = R(n,k,r).

Pro n=2, k=3 je r = 2³−1 = 7:

Periody

Výrazy tvaru s=∑x^u, kde u jsou instance jednoho určitého druhu R-systému, nazveme Gaussovými periodami. Každá perioda je charakterizována g-číslem druhu:    s_i/e = ∑x ^{g∙nj mod r} , kde j=0..k−1.

Perioda je netriviální, když má více než jeden člen, tj. když řád systému je větší než 1.

K označení jednotlivých součtů budeme používat zlomek i/e, kde e udává počet period příslušných danému systému, i pořadové číslo periody. Písmeno e udává počet Eulerových druhů (viz G-systémy). V prostých R-systémech (rεP) je e = v= (r−1)/k, kde v je počet vlastních druhů (viz G-systémy/Vnořování).

Pro r=5 existují dvě (netriviální) možnosti sestavení period.

 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)

Vztahy mezi součty

V daném systému budeme periody značit g_i = s_i/e, výrazy jsou vázány určitými vztahy.
Např.v R(4,2,5):

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

Protože je: 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))

platí:

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

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

Součet všech period

Součet čísla 1 a všech period g_i tvoří geometrickou posloupnost x^u se součtem:   1+∑g_i = ∑x^u = (x^r−1)/(x−1) = M(x,r)

Proto:

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

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

Součin členů period

Instance tvoří exponenty členů period, přičemž jedna perioda odpovídá jednomu druhu R-systému R(n,k,r). Protože součet instancí libovolného druhu je vždy dělitelný číslem r−1, platí analogický vztah pro součiny členů period:

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

Např. v R(4,2,5) je x ∙ x⁴ ≡ x² ∙ x³ ≡ 1 (mod M(x,5)).

Rozpad kongruence

Pokud je číslo n−1 mocninou čísla 2, řešení rovnice xⁿ = 1 se rozpadá jen na kvadratické rovnice. Trigonometrické funkce pro příslušné úhly je pak možné zapsat jen pomocí druhých odmocnin.
Např. Řešení kongruence x¹⁷−1 ≡ 0 (mod 103) závisí na E=φ(17)=16=2⁴. Stačí proto řešit čtyři kongruence druhého stupně.

Gaussovy periody

Gaussovy polygony

Pravidelný r-úhelník je snadné sestrojit pravítkem a kružítkem pro r=2^j (čtverec,osmiúhelník,...), r=3 (trojúhelník) i r=5 (pětiúhelník) a také pro kombinace: r=3∙2^j, r=5∙2^j a r=15∙2^j, jεN₀. Postupy byly známé již v době Euklidově. Gauss si povšiml (r.1796), že je možné sestrojit také 17-ti úhelník (φ(17)=2⁴), resp. každý p-úhelník pro Fermatova prvočísla p=2^(2t)+1 (viz F-systémy). Dokázal, že možnost konstrukce závisí na prvočíselném rozkladu čísla E=φ(n), tj. E=p−1 pro pεP (např. φ(3)=2¹ a φ(5)=2²).

Z kombinací (součinů) čísel n=2^j,3,5,17,257,65537,...vznikají tyto hodnoty r [Gauss I]:   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,..

Součiny lichých Fermatových čísel tvoří posloupnost: 3,5,15,17,51,85,255,257,... (viz Binární systémy.)

Prvky, které vznikají euklidovskými konstrukcemi (pravítkem a kružítkem), tj. souřadnice bodů, směrnice přímek, koeficienty v rovnicích kružnic,.., patří do oboru, který vznikne z oboru souřadnic doplněním jednoznačně určených druhých odmocnin (viz Rozšiřování oborů).

Pětiúhelník

V systému R(4,2,5) platí:    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)) 

Řešením kvadratické rovnice g²+g−1=0 je:

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

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

V tuto chvíli známe hodnoty pro x + x⁴ = g₀ a x² + x³ = g₁. K vyčlenění x z výrazu x + x⁴ = g₀ využijeme vztah pro součin členů period (viz výše).    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 

Do řešení x=x₁ kvadratické rovnice x² − g₀x + 1 = 0 dosadíme g₀ = (−1+√5)/2.    x₁ = (g₀+√(g₀²−4))/2   x₂ = (g₀−√(g₀²−4))/2    x = (−1+√5)/4 + i∙√2∙√(5+√5)/4

Sedmiúhelník

Podle modulu (mod M(x,7)):    g₀+g₁  ≡  −1  g₀∙g₁  ≡ g₀+g₁+3  =2

Z řešení kvadratické rovnice 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)

Vztahy mezi kořeny

Podle modulu M(x,7) platí např.:

·   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₂, tj.g₂ ≡ g₀(g₁−1),...

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

Odtud:

·   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₀)

Tedy (1−g₀²)/g₀ ≡ −1/(1+g₀) tj.:

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

Třináctiúhelník

V případě kongruence x¹³−1 ≡ 0 (mod 53) je E=φ(13)=12=2² 3¹. Řešení je nutné převést na 3 kongruence: dvě druhého a jednu třetího stupně.
Po kvadratických kongruencích s_0/2=g₀,s_1/2=g₁ (viz výše) dále následují:

     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)

Složené R-systémy

V složených R-systémech můžeme periody sestavit jen pro exponenty u nesoudělnými s r, (u,r) = 1. Např. G(2,4):   (1)   x   +  x² +  x⁴ ²+  x⁸   s_0/2    x³  +  x⁶  +  x¹² +  x⁹   x⁵  +  x¹⁰   x⁷  +  x¹⁴ +  x¹³ +  x¹¹   s_1/2   M(x,15)

Počet period je e=φ(r)/k.

Regulární prvočíslo

Přívlastek regulární získává prvočíslo p tehdy, když nedělí řád tělesa získaného doplněním p-tého (p=r−1) kořenu jednotky k racionálním číslům (více viz Algebraické rovnice/Rozšíření oborů).

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

Pro r= 7

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

α = (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

Kvadratický zákon reciprocity

Dosavadní poznatky nám mohou usnadnit hledání zbytků daných čísel podle určitého modulu. V této kapitole nahlédneme krátce (klasický, ale obtížný) problém inverzní. Budeme hledat všechny moduly, které dávají jeden určitý zbytek.

Číslo 2 kvadratickým zbytkem

Číslo 2 je kvadratickým zbytkem, když číslo u = a² mod r = 2 systému R(n,k,r) najdeme v prvním řádku.

    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 

 Podle Eulerova kriteria má být Q(2,r)=2^κ(r) mod r ≡ 1 (mod r), což platí pro následující moduly 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 

Hodnota a=√(2) (mod r). Např. √(2) (mod 7) = 3 protože 3² ≡ 2 (mod 7). Kvadratickým nezbytkem je číslo 2 pro ostatní neobsazená prvočíselná r,

tj. pro 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 

Gaussovo pravidlo

K určení, zda je číslo Z kvadratickým zbytkem (mod r) stačí znát velikosti zbytků z(k) = k∙Z mod r, kde k=1..κ(r). Kvadratickým zbytkem je číslo Z jen v tom případě, kdy mezi z(k) je počet zbytků větších než r/2 sudý.

Pro r=17, Z= 7 je κ(r)=8, r/2 = 8.5. Prvními 8 zbytky jsou:

   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 

Protože počet zbytků větších než 8.5 je lichý (jde o tři čísla: 11,14 a 15) je číslo 7 nezbytkem podle modulu 17.

Pro r=19 a r=23 ještě ověříme, zda Z=2 je kvadratickým zbytkem.

·    Mezi 9−ti zbytky (2,4,6,8,10,12,14,16,18) je 5 čísel větších než 9.5. Číslo 2 je kvadratickým nezbytkem (mod 19).

·    Pro r=23 mezi 11-ti zbytky (2,4,6,8,10,12,14,16,18,20,22) 6 čísel větších než 11.5. Číslo 2 je kvadratickým zbytkem (mod 23).

V případě Z=2 je z(k) = k∙Z. Sledovaný počet čísel závisí proto jen na tvaru čísla r resp. κ(r) (κ(19) = 9, κ(23) = 11).
Číslo 2 je kvadratickým zbytkem (mod r) tehdy, když κ(r) je ryzí liché číslo (tj. číslo tvaru 4s+1).

Rozložení zbytků a nezbytků

Ryzí lichá čísla

V kvadratických systémech R(n,k,r), kde r je ryzí liché číslo je číslo −1 vždy v druhém řádku. Proto zbytek kontrastní k danému zbytku má opačnou "polaritu": když u je kvadratickým zbytkem je −u = r−u kvadratickým nezbytkem.

Např.    v R(2,3,7) je číslo 2 kvadratickým zbytkem a číslo −2 nezbytkem,

·    v R(3,5,11) je číslo −2 kvadratickým zbytkem a číslo 2 nezbytkem,

·    v R(4,9,19) je číslo −2 kvadratickým zbytkem a číslo 2 nezbytkem.

  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

Neryzí lichá čísla

V kvadratických systémech R(n,k,r), kde r je neryzí liché číslo je číslo −1 vždy v prvním řádku. Proto se vzájemně kontrastní zbytky vyskytují v rámci téhož druhu.

Např.

·    v R(4,2,5) jsou čísla 1,−1 kvadratickými zbytky,

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

Modality prvočíselných modulů

Budeme hledat prvočíselné moduly r (resp. jejich mediány κ(r)), pro které je u kvadratickým zbytkem, tj. existuje takové číslo s, že s²≡u (mod r).
Když zapíšeme posloupnosti čísel κ(r) na kružnici, zjistíme, že existují určité periody opakování.

Předpokládejme nejprve rozdělení kružnice na 2∙u bodů. Když u je druhou mocninou (u=4,9,16,..) pokrývají hodnoty r všechna prvočísla. V ostatních případech pro pokrytí čísel κ(r) vystačíme jen s určitými body na kružnici.

Ať pokračujeme v posloupnosti čísel κ(r) jakkoliv daleko, nikdy (až na případ kdy u=a²) jejich obrazy nepokryjí celou kružnici, ale jen určité vybrané body. V hudební teorii se vžil pro takový výběr bodů termín modalita (Viz Hudební struktury).

Pro u=2..20 dostaneme modality:

 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,.... ──── 

·    Pro prvočíselná u má modalita u−1 hodnot.

·    Pro neryzí lichá u (tj.u tvaru 4s+1) je možné periodu zmenšit na polovinu, např.:

 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

Symetrie posloupností

Všechny v předchozím odstavci uvedené posloupnosti jsou symetrické, přičemž osa symetrie prochází mezi body 0 a 2u−1. Platí:

 ∑a ≡ 0 (mod 2u−1) 

kde a představují jednotlivá čísla posloupnosti (pro dané u). Např. 0+1+4+9+12+13 ≡ 0 (mod 13).

Přepišme všechna čísla vzhledem k bodu, kterým prochází osa symetrie, tj. k bodu −1/2.

 u  κ(r) mod 2u           K ose symetrie                    κ(r) mod u   K ose symetrie
──────────────────────────────────────────────────────────────────────────────────────────
 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   − 

Vztahy pro u=2,3,5

Pro u=2 i u=3 (a lichá r) je:

      κ(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) 

Případ u=5 je (vzhledem k tvaru 4s+1) možné převést ke stejným rovnicím s polovičním modulem (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). 

Proto u je kvadratickým zbytkem:

    u=2: když r²−1 je dělitelné 16, pak (r²−1)/8 je sudé  a r má tvar 8s±1.
    u=3: když r²−1 je dělitelné 24, pak (r²−1)/12 je sudé a r = 12s±1.
    u=5: když r²−1 je dělitelné 20, pak (r²−1)/10 je sudé a r = 10s±1. 

Vztahy pro u>5

Další případy redukovat není možné a jsou proto složitější.

Pro u=6:

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

Rovnici vyhovují čísla t tvaru 24s±1 a 24s±5.

Pro u=7:

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

Symetrie prvočísel

Prvočísla (z intervalu 1-50) rozepíšeme do řádek následujícím způsobem.

·   Prvním číslem v každém řádku bude pεP.

·    Za dvojtečkou necháme následovat jen taková čísla qεP, že q mod p je kvadratickým zbytkem podle modulu p:

·   Pokud q=p, zapíšeme q do závorky.

    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) 

 Dvě čísla, z nichž alespoň jedno není ryzí liché (např. 17 a 19), vytvářejí symetrický obraz v následujícím smyslu:
Číslo 17 je v 19-tém řádku a číslo 19 zase v řádku 17-tém.

Kvadratický zákon reciprocity

Odpovědí na otázku, kdy je zároveň číslo p kvadratickým zbytkem q (p ≡ a² mod q)
i číslo q kvadratickým zbytkem podle p (q ≡ b² mod p) je tzv. kvadratický zákon reciprocity:

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

Vztah objevil Legendre, speciální případy popsali před ním Euler a Lagrange. Gauss v teorii bikvadratických zbytků vztah zobecnil pro komplexní čísla.

Pro ryzí lichá čísla platí:

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

·   Q(p,q) = −Q(q,p),  tj. vztah reciprocity je antisymetrický (p,qεP, p,q>2)

Pro neryzí lichá čísla platí:

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

·    Q(p,q) = Q(q,p),  tj. vztah reciprocity je symetrický (p,qεP, p,q>2)

Důkaz zákona reciprocity

Kvadratické systémy

Kvadratické systémy R(p,k,r), kde k = κ(r) s počtem druhů e= (r−1)/k=2 rozdělíme na dvě skupiny podle hodnoty r (ryzí liché a neryzí liché).

Zajímat nás bude součin t_G =g₀g₁ v systémech s prvočíselným r.

Ryzí lichá 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

Neryzí lichá 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

Výpočet součinu

Součin t_G =g₀g₁ obsahuje v kvadratických systémech R(n,κ(r),r) vždy několik (řekněme c) součtů (s r-1 členy):  s_G = x+x²+... +x^r−1  a několik (řekněme J) jednotek, platí:

·    J= κ(r), když r je ryzí liché

·    J= 0, když r je neryzí liché

Všechna čísla pokrývají čtverec o hraně κ(r), tedy (r−1)∙c + J = κ²(r), tj. (po dosazení κ(r)=(r−1)/2):

·   c=(r−3)/4, když r je ryzí liché

·   c=(r−1)/4, když r je neryzí liché

Protože s_G = x+x²+... +x^r−1 ≡ −1 (mod M(x,r))  (viz Součet všech period),

je t_G = g₀g₁ = J − c, tj. (po dosazení za J a c):

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

Kořeny kongruence

Označme t=(1±r)/4, tedy ±r=4t−1. Proto r má tvar r=4s−1 (pro s=t) nebo r=4s+1 (pro s=−t). Ze vztahů:    s_G=g₀+g₁ ≡ −1 (mod M(x,r))    t_G=g₀g₁  ≡  t (mod M(x,r))

plyne kvadratická rovnice pro kořeny kongruence:

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

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

(? stupeň p i řád κ(r) jsou prvočíselné pεP (p>2), rεP ?)

Vlastní důkaz

 Pokusíme se porozumět Gaussovu důkazu zákona reciprocity (3.Gaussův důkaz), viz [Gauss II, Obecná pojednání o rovnicích, $366].

Cílem je dokázat, že pokud je ±p je kvadratickým zbytkem podle r je také r kvadratickým zbytkem podle p.

Když ±p je stupeň systému R(p,k,r) a leží v prvním ze dvou řádků R-systému, znamená to, že ±p je kvadratickým zbytkem podle modulu rεP.

V R(3,5,11) je +3,kvadratickým zbytkem mod 11; v R(4,10,13) je ±3 kvadratickým zbytkem 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

Když ±p je kvadratickým zbytkem podle r=4s±1, tak platí:

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

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

 (viz Gaussovy periody/Kvadratické systémy), tj. x²+x±s ≡ 0 (mod p)

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

V R(p,k,r) vždy platí r^k ≡ 1 (mod r). V případě kdy 2k|(p−1), tj. 2kv= (p−1) pro vεN. je r^(p−1)/2v ≡ 1 (mod r). Když je nějaké číslo kongruentní s jedničkou, je s jedničkou kongruentní i každá jeho mocnina, tedy také r^(p−1)/2 =r^κ(p) ≡ 1 (mod r) (viz Eulerovo kriterium). Tedy r kvadratickým zbytkem podle p.