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á kon^paience je řešitelná (a má 2 řešení), právě tehdy, když 219— =(21919\h 1 (mod 383). Ověření platnosti není bez použití výpočetnrPe^hniky 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
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^iVec/zr' p je liché prvočíslo, a, b G Z libovolná. Pak platí: =        (mod p).
(?) = ©©■
3. a = 6 (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~1 \ /    p—1 , ,       p — 1
protože p | ap    — 1 = (a~2~~ — l)(a~ + 1) nutně p \ a~ + 1, tj. a2^- = — 1 (mod p).
ad 2. Podle 1. dostáváme
( — ) = [ab)^ =        • 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. □
r^>)=~""^   ňiítiyi^      důsledek. 1. V libovolné redukované soustavě zbytků modulo p je i b J     yj    -ib<jhfy stejný počet kvadratických zbytků a nezbytků. ^ ~
* }J 2. Součin dvou kvadratických zbytků je zbytek, součin dvou nezbytků & l &\ I l-2/\*u%
f db \    (—\ /M      íe zbytek> součin zbytku^a nezbytku je nezbytek. f[ [ ^
v v) J        J uT 3. (—1/p) = (—1) 2 ; tj. kongruence x2 = —1 (mod p) je řešitelná i     #   .    .   . i
.«   .    právě tehdy, když p = 1 (mod 4). ^^^^Vj.vL
%L\19l DŮKAZ, ad 1. Kvadratické zbytky získáme tak, že všechny prvky 1 ' '
redukované soustavy zbytků umocníme na druhou. Těchto prvků je   ^^^3*^} ' 3j íj^
ave    2    ,> / i
p — 1, přitom druhé mocniny 2 prvků jsou spolu kongruentní právě tehdy, kdvž i e součet těchto prvků násobkem p. Máme tedy právě kvadratických zbytků, a tedy rovněž p—1 —      = í2^r kvadratických \jj nezbytků modulo p. Předpoklad, že p je prvočíslo, je podstatný - pro p^of-^}!^* faib)fa~é>J složená čísla je kvadratických nezbytků více než zbytků (viz dále část ' j o Jacobiho symbolu). f J 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 N 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. ^ ~3
Uvažujme množinu S nej menších zbytků (v absolutní hodnotě) mo- A dulo p. Je-li p prvočíslo, a E Z, p \ a, pak označíme /xp(a) počet
záporných nej menších zbytků (v absolutní hodnotě) čísel ^l'Af 2'4- %-0u
"       V t
P — 1 /J r
l-a,2-a,--a, "'v
'    '   2 /// «;
tj. pro každé z těchto čísel určíme, se kterým číslem z množiny S je  3 "*^/
kongruentní a spočítáme počet záporných z nich. ^"^J^i <L ^ ^ ^ Zf3j/
poznámka. Obvykle budou p a a zafixované, potom budeme místo ^1/ '
/ip(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. (yj?
Lemma (Gaussovo). Je-li p liché prvočíslo, a E Z, p \ a, pak   J>J^ (^J~ "/j
důkaz. Pro každé i E {1,2,...,        určíme m,t E {1, 2,..., ^*l^ ^Tiťfa)
tak, že i-a = ±mj (mod p). Snadno se vidí, že pokud k, l E {1, 2,..., ^^-j jsou různá, jsou různé i hodnoty mk,mi (nik = nii ==>- k ■ a = ±1 ■ a (mod p) ==>- k = ±/ (mod p), což nelze jinak, než že A; = _/).
Proto splývají množiny {1,2,..., ^^-j a {m1; m2,..., nip^i}. Vynásobením kongruencí
A
1 • a = dami    (mod p)
2 • a = i m2   (mod p)
p — 1
a
mP-i    (mod p)
dostáváme
| 2   ^       , "^f* fa - j té]
i /
• a^ = (—1)M /^—! I (mod p)
«*»)p^)«^<   14,I.Z,-M,W %^^yrW>'f Wfrb
52
(mezi pravými stranami je jich právě jj, záporných). Po vydělení obou
stran číslem ((p — l)/2)! dostáváme díky vztahu (a/p) = a 2 (mod p) požadované tvrzení. □
(^frxL ^"ftodf^A g využitím Gaussova lemmatu dokážeme hlavní větu této části, tzv.
" $ oC^hifr (^é(Áj   zákon kvadratické reciprocity.
VĚTA 32. Nechť p, q jsou lichá prvočísla. Pak
•44-       , , i.(f) = (-i)E?
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
/a I / *3M
f-tfK
ok
<bk\
2hk
ak p
ak p
ak p
ak p
i>4
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 sym-
bolem)- €L
Proto je
P
E2     r 2aki
Je-li navíc a liché, je a + p číslo sudé a dogtóváme
2a
P.
(-1)
2a + 2p p
p-i
^~r(a+p)fci
-<k=l í    p J
Celkem tak dostáváme (pro liché a
C
r)-(H)
(_i)eST[t] ■ (-i)
(28)
což pro a = 1 dává požadované tvrzení
n O
odu 2. , I ^ ,
53
Podle již dokázané části 2 a ze vztahu (28) dostáváme pro lichá čísla a
r ak i
Uvažme nyní pro daná prvočísla p ^ q množinu
T = {q-x- x E Z, 1 < x < (p-l)/2}x{p-y; y G Z, 1 < y < (g-l)/2}.
Zřejmě je \T\ =      ■      a ukážeme, že rovněž
r
(^V        *~     - (-1)ITI = (-l)Älf 1 . (_i)Efe1ľ[^
"     čímž budeme vzhledem k předchozímu hotovi. -f    y^4^ 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     ^a^"' že Tx = T D {[u,v]; u,v E 7j,u < v}, T2 = T \ T\. Zřejmě
je T\ počet dvojic [qx,py], kde x < |y. Protože |y < | •       < |, je
^?/^<        Pro pevné y tedy v"T\ leží právě ty dvojice [g:r,H/], pro které 1~ x </[f^Ttedy |Ti| = EÍ,',"11)/2[?»]- Analogicky |T2| =
Ľ?.~i1)/2[J4 ~-
Proto (|) = (—l)'Tl' a (|) = (—1)'T2' a zákon kvadratické reciprocity je dokázán. □
f^L\^ [r-A \ důsledek. 1. —1 je kvadratický zbytek pro prvočísla p splňující
l  "p J        */ 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). » 0-1 OľA      ^' ^e"^ P = 1 (mod 4) nefro g = 1 (mod 4), je (p/g) = (q/p), jinak
{~y       J'p =g =3 (mod 4^Je (p/g) =Qq/^-
příklad. Určete (j§^).
54
\t MÍiJcU Řešení.
^•^'Zjcj (ftocf^^)\     (j^It) ^\^9^j neboť 101 dává po děleni 4 zbytek 1
neboť 79 dává po děleni 8 zbytek -1 neboť 11 i 79 dávají po dělení 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. £ ^ p^Mlo
Definice. Nechť a e Z, &^ej^ 2 \b. Nechť b = pxp2 • • ~Pk 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
bj     \p±J   \p2J \Pk 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 6).
®-4 «1%
příklad, a přitom kongruence
x2 = 2   (mod 15) ^
není řešitelná (není totiž řešitelná kongruence x2 = 2 (mod 3) a není ani řešitelná kongruence x2 = 2 (mod 5)).
55
Tvrzení 4.7. Nechí b, b' g N jsou lichá, g Z libovolná.
Pak platí:
1. ai = a2 (mod 6) =^ (f) = (f), 3- =
Lemma. Buďte a, b g n lichá. Pak platí
1. 2ti = «_i + £_i (mod 2),
2. ^ti = 2ti + ^i (mod 2).
Důsledek. Pro g N /zc/za p/aíz'
Eľ=i = nľ-12afc~1 (mod 2), Eľ^^-11^ (mod 2).
Věta 33. iVec/zŕ7 a, 6 g N json /zcM. PaA;
2- (I) = ("l)i
5- (!) (!) = (-
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\ _ /383W
ÍJacobí) 383 i 219 dávají po dělení Á zbytek 3 383/       V 219/ ( J
164\__/ ^    I   / ÍL
219/
41 219 219' U 14' 41
2 \ / 7
164 = 22 -41
(Jacobí) neboť 41 dává po dělení 4 zbytek 1
AI j \41 7_ 41 41
y
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 foaO( je dané číslo a kvadratickým zbytkem? (tuto otázku již umíme od-
fo*\    £ povědět např. pro a = 2). Prvním krokem je zodpovězení této otázky
tp/" ' pro prvočísla.
\dt*0* °\ fCdí/( VĚTA 34. Nechť q je Uché prvočíslo.
fojj %lyJlL ha0( • 3e-ti 9 = 1 (mod 4), pak je q kvadratický zbytek modulo ta
PÍ 1 prvočísla p, která splňují p = r (mod q), kde r je kvadratický
7 tť/i»~ / 3" £ f zbytek modulo q.
-2_       ,        1 ,« • 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-X,7^)! JI ~$ procity. Nechť tedy q = 3 (mod 4), tj. (q/p) = (-l)2^(p/q). Nechť
nejprve p = +b2 (mod Aq), kde b je liché. Pak p = b2 = 1 (mod 4) a i^bj 4 j p = b2 (mod q). Tedy (-1)^ = 1 a (p/q) = 1, odkud (q/p) = 1. Je-li
hio bitek O h       nyní p = —b2 (mod Aq), pak obdobně p = —b2 = 3 (mod 4) a p = —b2 Ol ^óLjSl^     ^mod ^' Tedy = "I a (p/tf) =      odkud opět (g/p) = 1.
57
Obráceně, mějme (q/p) = 1. Máme dvě možnosti - buď (—1)~ = 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 b 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 (mod4g). ^        □ 9d
PŘIKLAD. Určete modulo která prvočísla je       *_ /
b) -s   r ^^tv v
kvadratickým zbytkem. i , .
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. Nechííp = 3 (mod 4), a e Z splňuji (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.