45
• m = 2 nebo m = A,
• m je mocnina lichého prvočísla
• m je dvojnásobek mocniny lichého prvočísla.
poznámka. Pokud pro přirozené číslo existují primitivní kořeny, tak jich mezi čísly 1,2,... ,m existuje právě y?(y?(m)). Je-li totiž g primitivní kořen a a G {1,2,..., íp(m)} libovolné, pak ga je podle Věty 19 řádu (ay(m))' co^ Je rovno f(m) právě tehdy, je-li (a,<p(m)) = 1. Takových a je v množině {1,2,..., íp(m)} právě y?(y?(m)).
Důkaz Věty provedeme v několika krocích. Snadno je vidět, že primitivní kořen modulo 2 je 1 a modulo 4 je 3. Dále ukážeme, že primitivní kořeny existují modulo libovolné liché prvočíslo (pro ty, kdo si pamatují základy algebry, tak vlastně jiným způsobem dokážeme, že grupa (Z^, •) invertibilních zbytkových tříd modulo prvočíselné m je cyklická.
tvrzení 4.1. Nechť p je liché prvočíslo. Pak existují primitivní kořeny modulo p.
důkaz. Označme r1; r2,..., rp_! řády čísel 1, 2,... ,p — 1 modulo p. Buď ô = [r1; r2,..., rp_i] nejmenší společný násobek těchto řádů. Ukážeme, že mezi čisly 1,2,... ,p— 1 existuje číslo řádu ô a že ô = p— 1.
Nechť ô = g"1 • • • q^h je rozklad ô na prvočísla. Pro libovolné s G {1,... k} existuje c G {1,... ,p — 1} tak, že g"s | rc (jinak by existoval menší společný násobek čísel r\, r2,..., rp_i než je ô), tj. ex. b G Z tak, že rc = b - g"s. Protože c má řád rc, má číslo gs := cb podle Věty 19 řád
Provedením předchozí úvahy pro libovolné s G {1,... k} dostaneme gi,..., gk a můžeme položit g := g± - ■ ■ gk- Podle Lemmatu za Větou 19 dostáváme, že řád g je roven součinu řádů čísel g±,. ■ ■ ,gk, tj. číslu
gr---gr = č.
Nyní dokážeme, že ô = p — 1. Protože řády čísel 1, 2,... ,p — 1 dělí 5, dostáváme pro libovolné x E {1,2,... ,p — 1} vztah xs = 1 (mod p). Kongruence stupně ô modulo p má podle Věty 26 nejvýše ô řešení (a podle předchozího má p — 1 řešení), proto nutně ô > p — 1. Přitom ó \ p — 1 (jakožto řád čísla g), proto zejména ô < p — 1, a celkem 5 = p-l. □
Nyní ukážeme, že primitivní kořeny existují dokonce modulo mocniny lichých prvočísel. K tomuto budeme potřebovat dvě pomocná tvrzení.
Lemma. Bud' p liché prvočíslo, l > 2 libovolné. Pak pro libovolné a G Z platí
(1 + ap)pl 2 = 1 + ap1^1   (mod pl).
46
důkaz. Plyne snadno z binomické věty s využitím matematické indukce.
I. Pro / = 2 tvrzení zřejmě platí.
II. Nechť tvrzení platí pro /, dokážeme jej i pro / + 1. S využitím Lemmatu na str. 23 tak umocněním na p-tou tvrzení pro / (s navýšením modulu) dostaneme
(1 + apý'1 = (1 + apř-y   (mod pl+1). Z binomické věty přitom plyne
(1 + aPl-vY = 1 + p ■ a ■ p1'1 +      (fy akP(l-1)k
k=2 ^ '
a vzhledem k tomu, že pro 1 < k < p platí p \ (^)? stačí ukázat pi+i | pi+(i-i)k^ CQ~ je ekvivalentní s 1 < (k — 1)(/ — 1). Rovněž pro k = p dostáváme díky / > 3 vztah pl+1 | p(ř_1)p.
□
Lemma. Buď p liché prvočíslo, l > 2 libovolné. Pak pro libovolné a G Z, splňující p \ a platí, že řád čísla 1 + ap modulo pl je roven pl~x.
důkaz. Podle předchozího Lemmatu je
(1 + apf1'1 = l + apl   (mod pl+1),
a uvážíme-li tuto kongruenci modulo pl, dostaneme (1 + ap)pl 1 = 1 (mod pl). Přitom přímo z předchozího Lemmatu a faktu p \ a plyne (1 + ap)p    ^ 1 (mod pl), což dává požadované. □
tvrzení 4.2. Bud' p liché prvočíslo. Pak pro každé l G n existuje primitivní kořen modulo pl.
důkaz. Nechť g je primitivní kořen modulo p. Ukážeme, že pokud gP-i ^ ^ (mod p2), je g dokonce primitivním kořenem modulo pl pro libovolné / G N. (Pokud by platilo gp~ľ = 1 (mod p2), pak (g + pY^1 = l + (p— l)gp~2p ^ 1 (mod p2), a tedy místo g můžeme volit za původní primitivní kořen číslo g + p.)
Nechť tedy g splňuje gp~ľ ^ 1 (mod p2). Pak existuje a G Z, p \ a tak, že gp~ľ = 1 + p ■ a. Ukážeme, že g je modulo pl řádu ip{pl) = {p — l)pz_1. Buď n G N nejmenší číslo, splňující gn = 1 (modpz). Podle předchozího Lemmatu je gp~ľ = 1 + p ■ a řádu pl~ľ modulo pl. Pak ale
(gp-1)n = (gn)p-1 = 1    (mod p1) =^ p1'1 | n.
Zároveň z gn = 1 (mod p) plyne p — 1 | n. Protože jsou čísla p — 1 a pl~ľ nesoudělná, dostáváme (p — l)pz_1 | n. Proto n = ip{pl) a g je tedy primitivní kořen modulo pl. □
tvrzení 4.3. Buď p liché prvočíslo a g primitivní kořen modulo pl pro l G N. Pak liché z čísel g,g + pl je primitivním kořenem modulo 2pl.
47
důkaz. Nechť c je liché přirozené číslo. Pak pro libovolné n G N platí cn = 1 (mod pl), právě když cn = 1 (mod 2pl). Protože tp(2pl) = (f{pl)i Je každý lichý primitivní kořen modulo pl rovněž primitivním kořenem modulo 2pl. □
Další tvrzení popisuje případ mocnin sudého prvočísla. K tomu využijeme obdobných pomocných tvrzení jako v případě lichých prvočísel
Lemma. Buď l G N, l > 3. Pak 52i~3 = 1 + 21'1 (mod 2ř).
důkaz. Obdobně jako výše pro 2 \p. □
Lemma. Bud l G N, / > 3. Pak řád čísla 5 modulo 2ř je 2ř~2.
důkaz. Snadný z předchozího Lemmatu. □
tvrzení 4.4. Nechi l G n. Primitivní kořeny existují modulo 2l právě tehdy, když l < 2.
důkaz. Buď / > 3. Pak množina
S = {(-l)a • 56; a G {0,1}, 0 < b < 2ř~2; b G Z}
tvoří redukovanou soustavu zbytků modulo 2Z (má totiž tp(2l) prvků o kterých se snadno ukáže, že jsou po dvou nekongruentní modulo 2Z).
Přitom zřejmě (s využitím předchozího Lemmatu) řád každého prvku S dělí 2Z~2, proto v této (a tedy ani v žádné jiné) redukované soustavě nemůže existovat prvek řádu tp(2l) = 2l~1. □
Posledním kamínkem do mozaiky tvrzení, která společně dokazují Větu 30, je tvrzení popisující neexistenci primitivních kořenů pro složená čísla, která nejsou mocninou prvočísla (ani jejím dvojnásobkem).
tvrzení 4.5. Nechi m G n je dělitelné alespoň 2 prvočísly a není dvojnásobkem mocniny lichého prvočísla. Pak modulo m neexistují primitivní kořeny.
důkaz. Buď rozklad m na prvočísla tvaru 2ap"1 • • -p^.k, kde a G No, cti G N, 2 { pi a buď platí k > 2 nebo k > 1 a a > 2. Označíme-li ô = [^(2a),^(p^),..., ipipi1)], pak se snadno vidí, že ô < ^(2a) ■ VÍPí1)''' VÍPí1) = f(,m) a ze Pro libovolné a G Z, (a, m) = 1 platí as = 1 (mod m). Proto modulo m neexistují primitivní kořeny. □
Nyní máme dokázáno tvrzení přesně charakterizující ty moduly, pro které existují primitivní kořeny. Obecně je ale pro daný modul nalezení primitivního kořene velmi výpočetně náročná operace. Následující věta nám udává ekvivalentní podmínku pro to, aby zkoumané číslo bylo primitivním kořenem, jejíž ověření je o něco snazší než přímý výpočet řádu tohoto čísla.
48
věta 31. Buď m takové, že modulo m existují primitivní kořeny. Zapišme y?(m) = 1 • • • q^h. Pak pro libovolné g G Z, (g, m) = 1 platí, že g je primitivní kořen modulo m, právě když
íf(m) y(m)
g n   ^1   (modm),...,g      ^1   (mod m).
důkaz. Pokud by platila některá z uvedených kongruencí, znamenalo by to, že řád g je menší než íp(m).
Obráceně, pokud g není primitivní kořen, pak existuje d G N, d \ <f(m), kde d < <f(m) a gd = 1 (mod m). Je-li -u = > 1, nutně
existuje i G {1,..., k} tak, že qt | u. Pak ale
g ii   = g ii = 1   (mod m).
□
příklad. Postupně určíme primitivní kořeny modulo 41,412 a 2 •
412.
Řešení. Protože y?(41) = 40 = 23 • 5, je libovolné celé číslo g, které je s 41 nesoudělné, primitivním kořenem modulo 41 právě tehdy, když
g20 ž 1   (mod 41) A g8 ^ 1   (mod 41). g = 2:   28 = 25 • 23 = -9 • 8 = 10   (mod 41)
220 = (25)4 _ (_g)4 = gl2 _ (_^2 = X     (mod 41)
g = 3:   38 = (34)2 = (-1)2 = 1   (mod 41) g = 4 :   řád 4 = 22 vždy dělí řád 2
g = 5 :   58 = (52)4 = (-24)4 = 216 = (28)2 = 102 = 18   (mod 41)
520 = (52)10 _ (_24)10 = 240 = (220)2 _ x     (mod 41)
^ = 6 :   68 = 28 • 38 = 10 • 1 = 10   (mod 41)
g20 = 220 . 320 _ 220 . (38)2 .34 = !^. = _X     (mod ^
Dokázali jsme tak, že 6 je (nejmenší kladný) primitivní kořen modulo 41 (pokud by nás zajímaly i ostatní primitivní kořeny modulo 41, tak bychom je dostali umocněním 6 na všechna čísla od 1 do 40, která jsou se 40 nesoudělná - je jich právě y?(40) = y?(23 • 5) = 16 a jsou jimi tyto zbytky modulo 41: ±6, ±7, ±11, ±12, ±13, ±15, ±17, ±19.
Dokážeme-li nyní, že 640 ^ 1 (mod 412), budeme vědět, že 6 je i primitivním kořenem modulo libovolná mocnina 41 (pokud bychom „měli smůlu" a 640 = 1 (mod 412), pak by primitivním kořenem modulo 412 bylo číslo 47 = 6 ±41). Při ověření podmínky si vypomůžeme několika triky (tzv. modulární reprezentace čísel), abychom se obešli bez manipulace s velkými čísly.
Nejprve vypočtěme zbytek po dělení 68 číslem 412; k tomu se nám bude hodit vypočítat zbytek po dělení čísel 28 a 38:
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.