49
28 = 256 = 6 • 41 + 10
38 = (34)2 = (2 • 41 - l)2 = -4 • 41 + 1   (mod 412) Pak 68 = 28 • 38 = (6 • 41 + 10)(-4 • 41 + 1) =
=-34-41 + 10 = 7-41 + 10 (mod412) a 640 = (68)5 = (7 • 41 + 10)5 = (105 + 5 • 7 • 41 • 104) = = 104(10 + 35 • 41) = (-2 • 41 - 4)(-6 • 41 + 10) = = (4-41 -40) = 124 ^ 1 (mod412).
Přitom jsme využili toho, že 104 = 6 • 412 - 86, tj. 104 = -2 • 41 - 4 (mod 412).
Je tedy 6 primitivním kořenem modulo 412 a protože je to sudé číslo, je primitivním kořenem modulo 2-412 číslo 1687 = 6 + 412 (nejmenším kladným primitivním kořenem modulo 2 • 412 je přitom číslo 7).
4.6. Kvadratické kongruence a Legendreův symbol. Naším úkolem bude najít jednodušší podmínku, jak zjistit, jestli je řešitelná (a případně, kolik má řešení) kvadratická kongruence
Z obecné teorie, uvedené v předchozích odstavcích, je snadné vidět, že k rozhodnutí, je-li tato kongruence řešitelná, stačí určit, je-li řešitelná (binomická) kongruence
kde p je liché prvočíslo a a číslo s ním nesoudělné.
Pro určení řešitelnosti kongruence (27) můžeme samozřejmě využít Větu 27, její využití ale často naráží na výpočetní složitost, proto se v kvadratickém případě snažíme najít kritérium jednodušší na výpočet.
příklad. Určete počet řešení kongruence x2 = 219 (mod 383).
Řešení. Protože 383 je prvočíslo a (2, </?(383)) = 2, z Věty 27 plyne, že daná kongruence je řešitelná (a má 2 řešení), právě tehdy, když 219— = 219191 = 1 (mod 383). Ověření platnosti není bez použití výpočetní techniky snadné (i když je to pořád ještě „na papíře" vyčíslitelné). Závěrem této části tuto podmínku ověříme s pomocí Legendreova symbolu daleko snadněji.
Definice. Nechť je p liché prvočíslo. Legendreův symbol definujeme předpisem
ax2 + bx + c = 0   (mod m).
x2 = a   (mod p)
(27)
1     p \ a, a je kvadratický zbytek modulo p, 0     p | a,
— 1   p \ a, a je kvadratický nezbytek modulo p.
50
PŘÍKLAD. Protože je kongruence x2 = 1 (mod p) řešitelná pro libovolné liché prvočíslo p, je (1/p) = 1.
(—1/5) = 1, protože kongruence x2 = — 1 (mod 5) je ekvivalentní s kongruencí x2 = 4 (mod 5), jejímiž řešeními jsou x = ±2 (mod 5).
Lemma. Nechi p je liché prvočíslo, a, b g Z libovolná. Pak platí: 1. (-) = aV (mod p).
(?) = ©©■
5. a = b (modp) g) = g).
DŮKAZ, ad 1. Pro p | a je tvrzení zřejmé; pokud je a kvadratický zbytek modulo p, pak tvrzení plyne z Věty 27. Z téže věty plyne,
p—1
že v případě kvadratického nezbytku je ^ 1 (mod p). Pak ale,
i 1 /    P~l \ /    p—1 , , p—1
protože p | ap    — 1 = (a~2~~ — \)[a~ + 1) nutně p \ a~ + 1, tj. = — 1 (mod p). ad 2. Podle 1. dostáváme
( — ) = (aĎ)^" =        • b^ = (-) (-)    (mod p). \pj \Pj XPJ
Protože jsou hodnoty Legendreova symbolu z množiny { — 1,0,1}, plyne z kongruence (ab/p) = (a/p)(b/p) (mod p) přímo rovnost.
ad 3. Zřejmé z definice. □
DŮSLEDEK. 1. V libovolné redukované soustavě zbytků modulo p je stejný počet kvadratických zbytků a nezbytků.
2. Součin dvou kvadratických zbytků je zbytek, součin dvou nezbytků je zbytek, součin zbytku a nezbytku je nezbytek.
3. (—1/p) = (—1)^, tj. kongruence x2 = — 1 (mod p) je řešitelná právě tehdy, když p = 1 (mod 4).
DŮKAZ, ad 1. Kvadratické zbytky získáme tak, že všechny prvky redukované soustavy zbytků umocníme na druhou. Těchto prvků je p—1, přitom druhé mocniny 2 prvků jsou spolu kongruentní právě tehdy, když je součet těchto prvků násobkem p. Máme tedy právě kvadratických zbytků, a tedy rovněž p—1 — = í2~^~ kvadratických nezbytků modulo p. Předpoklad, že p je prvočíslo, je podstatný - pro složená čísla je kvadratických nezbytků více než zbytků (viz dále část o Jacobiho symbolu).
ad 2. Tvrzení je zřejmé z předchozího lemmatu.
ad 3. Zřejmé. □
Již s využitím těchto základních tvrzení o hodnotách Legendreova symbolu jsme schopni dokázat větu o nekonečnosti počtu prvočísel tvaru 4A; + 1.
TVRZENÍ 4.6. Prvočísel tvaru Ak + 1 je nekonečně mnoho.
51
důkaz. Sporem. Předpokládejme, že p±,P2, ■ ■ ■ ,Pi jsou všechna prvočísla tvaru Ak + 1 a uvažme číslo N = (2pi ■ ■ ■pi)2 + 1. Toto číslo je opět tvaru Ak + 1. Pokud je iV prvočíslo, jsme hotovi (protože je jistě větší než kterékoli z p1}p2, ■ ■ ■ ,pi), pokud je složené, musí existovat prvočíslo p, dělící N. Zřejmě přitom žádné z prvočísel 2,p1,p2> • • • ,Pi není dělitelem N, proto stačí dokázat, že p je rovněž tvaru Ak + 1. Protože ale (2pi---pi)2 = —1 (modp), dostáváme, že (—1/p) = 1, a to platí právě tehdy, je-li p = 1 (mod 4). □
Nyní odvodíme další pravidla pro výpočet Legendreova symbolu.
Uvažujme množinu S nej menších zbytků (v absolutní hodnotě) mo-dulo p. Je-li p prvočíslo, a G Z, p \ a, pak označíme fip(a) počet záporných nej menších zbytků (v absolutní hodnotě) čísel
tj. pro každé z těchto čísel určíme, se kterým číslem z množiny S je kongruentní a spočítáme počet záporných z nich.
poznámka. Obvykle budou p a, a zafixované, potom budeme místo jJLp{a) psát jen fi.
příklad. Vypočtěte hodnotu fi pro p = 11, a = 3.
řešení. S = {-5,-4,-3,-2,-1,1,2,3,4,5}. Protože 1-3 = 3, 2-3 = —5,3 • 3 = —2,4-3 = 1,5-3 = 4 (mod 11), dostáváme fi = 2.
Lemma (Gaussovo). Je-li p liché prvočíslo, a G Z, p \ a, pak
důkaz. Pro každé i G {1,2,..., ^} určíme m, G {1,2,...,^} tak, že i-a = ±mj (mod p). Snadno se vidí, že pokud k, l G {1, 2,..., ^^-j
1 • a, 2 • a,...
p — 1
■ a
2
±/ • a
Proto splývají množiny {1,2,..., a {m1; m2,..., mP-i kongruencí
}. Vynásob
1 ■ a = iíľii   (mod p)
2 ■ a = ±m2   (mod p)
p — 1
• a = ±mP-i
(mod p)
2
dostáváme
P
1
! • a 2 =
(-1)
p — 1
!   (mod p)
2
2
52
(mezi pravými stranami je jich právě fi záporných). Po vydělení obou
P-i
stran číslem ((p — l)/2)! dostáváme díky vztahu (a/p) = a 2 (mod p) požadované tvrzení. □
S využitím Gaussova lemmatu dokážeme hlavní větu této části, tzv. zákon kvadratické reciprocity.
věta 32. Nechť p, q jsou lichá prvočísla. Pak
' (?) = (-D2*1 «■ © = (-D^
důkaz. Věta se v tomto tvaru uvádí zejména proto, že pomocí těchto tří vztahů a základních pravidel pro úpravy Legendreova symbolu jsme schopni vypočítat hodnotu (a/p) pro libovolné celé číslo a. První část tvrzení již máme dokázánu, v dalším nejprve odvodíme mezivýsledek, který využijeme k důkazu zbylých částí. Poznamenejme rovněž, že v literatuře existuje mnoho různých důkazů této věty (v roce 2010 uváděl F. Lemmermeyer 233 důkazů), obvykle ovšem využívajících (zejména u těch stručnějších z nich) hlubších znalostí z algebraické teorie čísel.
Nechť je dále a g Z, p \ a, A; g N a nechť [x] (resp. (x)) značí celou (resp. necelou) část reálného čísla x. Pak
~2ak~			ak	1 ak\		ak		/ ak\
		1		+ 2( —)	= 2		+	2( —)
. P .			. P .	\P 1 _		. P .		_ \ P 1 _
Tento výraz je lichý právě tehdy, když je (—) > |, tj. právě tehdy, je-li nejmenší zbytek (v absolutní hodnotě) čísla ak modulo p záporný (zde by měl pozorný čtenář zaznamenat návrat od výpočtů zdánlivě nesouvisejících výrazů k podmínkám souvisejícím s Legendreovým symbolem). Proto je
-J  = (-lf = (-l)E*=l '"F].
Je-li navíc a liché, je a + p číslo sudé a dostáváme
Í2a\ = /2a + 2p\ = /4^\ = /2\2   /^_\ = \P)      V    P     )      \  P  )      \Pj     \ P ) = (_i)ESľ[^] = (_!)EfeX[f 1 . (_i)£2ľ*.
Celkem tak dostáváme (pro liché a)
což pro a = 1 dává požadované tvrzení z bodu 2.
53
Podle již dokázané části 2 a ze vztahu (28) dostáváme pro lichá čísla a
g) = (-DE"
Uvažme nyní pro daná prvočísla p ^ q množinu
T = {q-x; x G Z, 1 < x < (p-l)/2} x {p-y; y G Z, 1 < y < (g-l)/2}.
Zřejmě je \T\ = ^y- '      a ukážeme, že rovněž
p—1 p—1
(-l)m = (_i)Efc"2T[f 1 . (_i)Efe"I7[f ]; (29)
čímž budeme vzhledem k předchozímu hotovi.
Protože pro žádná x,y z přípustného rozsahu nemůže nastat rovnost qx = py, můžeme množinu T rozložit na dvě disjunktní podmnožiny T\ a T2 tak, že T\ = T H {[u, v]; u, v G Z, u < v}, T2 = T \ T\. Zřejmě je T\ počet dvojic [qx,py], kde x < |y. Protože |y < | • ^y- < |, je
< ^2^"- Pro pevné y tedy v T\ leží právě ty dvojice [qx,py], pro
které 1 < x < [^y], a tedy |Ti| = X^i^tfž/]- Analogicky |T2| =
Efc1,/2[J4
Proto (|) = (—l)'Tl' a (|) = (—1)'T2' a zákon kvadratické reciprocity je dokázán. □
důsledek. 1. — 1 je kvadratický zbytek pro prvočísla p splňující p = 1 (mod 4) a nezbytek pro prvočísla splňující p = 3 (mod 4).
2. 2 je kvadratický zbytek pro prvočísla p splňující p = ±1 (mod 8) a nezbytek pro prvočísla splňující p = ±3 (mod 8).
3. Je-li p = 1 (mod 4) nebo q = 1 (mod 4), je (p/q) = (q/p), jinak (tj. p = q = 3 (mod A)) je (p/q) = - (q/p).
příklad. Určete (j§^).
54
Řešení.
101 ~79
neboí 101 dává po dělení 4 zbytek 1
neboí 79 dává po děleni 8 zbytek -1
neboí 11 i 79 dávají po děleni 4 zbytek 3
neboí 11 dává pod dělení 8 zbytek 3
4.7. Jacobiho symbol. Vyčíslení Legendreova symbolu (jak jsme viděli i v předchozím příkladu) umožňuje používat zákon kvadratické reciprocity jen na prvočísla a nutí nás tak provádět faktorizaci čísel na prvočísla, což je výpočetně velmi náročná operace. Toto lze obejít rozšířením definice Legendreova symbolu na tzv. Jacobiho symbol s podobnými vlastnostmi.
Definice. Nechť a e Z, b e N, 2 \ b. Nechť b = pľp2 ■ ■ -pu je rozklad b na (lichá) prvočísla (výjimečně neseskupujeme stejná prvočísla do mocniny, ale vypisujeme každé zvlášť, např. 135 = 3-3-3-5). Symbol
se nazývá Jacobiho symbol.
Dále ukážeme, že Jacobiho symbol má podobné vlastnosti jako Legendreův symbol (s jednou podstatnou odchylkou). Neplatí totiž obecně, že z (a/6) = 1 plyne řešitelnost kongruence x2 = a (mod b).
příklad.
není řešitelná (není totiž řešitelná kongruence x2 = 2 (mod 3) a není ani řešitelná kongruence x2 = 2 (mod 5)).
a přitom kongruence
2   (mod 15)
55
Tvrzení 4.7. Nechí b, b' g n jsou lichá, g Z libovolná.
Pak platí:
1. ai = a2 (mod o) =^ (f) = (f), 3- =
Lemma. Buďte a, b g n lichá. Pak platí
1. 2ti = «_i + £_I (mod 2),
2. = 2f_i +        (mod 2).
Důsledek. Pro g n lichá platí
1- Eľ=i = Uľ=\ak~1 (mod 2), 2. Eľ^^-11^ (mod 2).
Věta 33. iVec/zŕ7 a, 6 g n json /zcM. PaA;
1- S) = (-l)^ (I) = ("I)
5- (!)© = (-!)"•
2_
a-1 b-1
důkaz. Snadný. □
4.8. Aplikace Legendreova a Jacobiho symbolu. Primární motivací k zavedení Jacobiho symbolu byla potřeba vyčíslení Legendreova symbolu (a tedy rozhodnutí o řešitelnosti kvadratických kongru-encí) bez nutnosti rozkladu čísel na prvočísla. Ukažme si proto příklad takového výpočtu.
příklad. Rozhodněte o řešitelnosti kongruence x2 = 219 (mod 383).
56
řešení. 383 je prvočíslo, proto bude kongruence řešitelná, bude-li Legendreův symbol (219/383) = 1.
219 \ /383\
) = — I-) (Jacobi) 383 i 219 dávají po dělení 4 zbytek 3
3837 V219/ 164\ 219/
41 219 219 ~4T 14 41
AI J \41 7_ 41 41
y
164 = 22 -41
(Jacobi) neboť 41 dává po dělení 4 zbytek 1
neboi 41 dává pod dělení 8 zbytek 1 neboi 41 dává pod dělení 4 zbytek 1
) = 1 neboť 7 dává po dělení 4 zbytek 3.
Další aplikací je v jistém smyslu opačná otázka: Pro která prvočísla je dané číslo a kvadratickým zbytkem? (tuto otázku již umíme odpovědět např. pro a = 2). Prvním krokem je zodpovězení této otázky pro prvočísla.
věta 34. Nechť q je liché prvočíslo.
• je-li q = 1 (mod 4), pak je q kvadratický zbytek modulo ta prvočísla p, která splňují p = r (mod q), kde r je kvadratický zbytek modulo q.
• je-li q = 3 (mod 4), pak je q kvadratický zbytek modulo ta prvočísla p, která splňují p = ±b2 (mod Aq), kde b je liché a nesoudělné s q.
DŮKAZ. První tvrzení plyne triviálně ze zákona kvadratické reci-procity. Nechť tedy q = 3 (mod 4), tj. (q/p) = (—\)~(p/q). Nechť nejprve p = +b2 (mod Aq), kde b je liché. Pak p = b2 = 1 (mod 4) a p = b2 (mod q). Tedy (—l)2^- = 1 a (p/q) = 1, odkud (q/p) = 1. Je-li nyní p = —b2 (mod Aq), pak obdobně p = —b2 = 3 (mod 4) a p = —b2
p—l
(mod q). Tedy (—l)" = — 1 a (p/q) = —1, odkud opět (q/p) = 1.
57
Obráceně, mějme (q/p) = 1. Máme dvě možnosti - buď (—1) 2 = 1 a (p/q) = 1, nebo (—1)^ = — 1 a (p/g) = —1. V prvním případě je p = 1 (mod 4) a existuje 6 tak, že p = b2 (mod g) (lze přitom předpokládat, že 6 liché). Pak ale b2 = 1 = p (mod 4) a celkem p = b2 (mod 4g). V druhém případě je p = 3 (mod 4) a existuje b liché tak, že p = — b2 (mod g). Tedy — b2 = 3 = p (mod 4) a celkem p = —b2 (mod 4g). □
PŘÍKLAD. Určete modulo která prvočísla je
a) 3
b) -3
c) 6
kvadratickým zbytkem.
Následující tvrzení ukazuje, že pokud je modul kvadratické kongru-ence prvočíslo splňující p = 3 (mod 4), pak umíme nejen rozhodnout o řešitelnosti kongruenci, ale rovněž popsat všechna řešení.
TVRZENÍ 4.8. Nechi p = 3 (mod 4), a G Z splňují (a/p) = 1. Pak má kongruence x2 = a (mod p) řešení
x = ia2^   (mod p).
DŮKAZ. Ověříme snadno zkouškou
/ £+ín2      £+i (a\ /    j \
a 4     = a 2  = a ■   —   = a   (mod p).
□
Pro dokreslení obrazu o kvadratických zbytcích a nezbytcích formulujeme ještě jedno tvrzení (pro nepříliš obtížný důkaz euklidovského typu viz [3]).
VĚTA 35. Nechi a G N není druhou mocninou. Pak existuje nekonečně mnoho prvočísel, pro která je a kvadratickým nezbytkem.