• 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 G {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é^       p' *ä/\ indukce. (rflQpJ *ÁWlý U)
/   /*~\ I. Pro / = 2 tvrzení zřejmě platí. p '
AtŽlo (m J II. Nechť tvrzení platí pro /, dokážeme jej i pro / + 1. S využitím/.        a   /   /    . jP
\h Lemmatu na str. 23 tak umocněním na p-tou tvrzení pro / (s navýšenímy* typ J        ylfCfP I
í   H\^\      m°dulu) dostaneme \^      ''
OTzt iď J (1 + apf-1 = (1 + ajŕ-'Y   (modpW). f
Z binomické věty přitom plyne BnU^L p \^
(i + aj-y = i+P.a. p1-1 +   (fc)flV'-1)fc 4^fL
a vzhledem k tomu, že pro 1 < k < p platí p \ (p), stačí ukázat J^fJf é/j j/l-j)"*
pi+i | jfQ(i-i)k^ cog je ekvivalentní s 1 < {k —       — 1). Rovněž pro - *
A; = p dostáváme díky / > 3 vztah pz+1 | p(ř_1)p. (£-"7/*'/7 -• \*-*4)k.
Lemma. -Bnď p /zc/zé prvočíslo, l > 2 libovolné. Pak pro libovolné —-J a g Z, splňujíc^í^cfrylatí, že řád čísla 1 + ap modulo pl je roven pl~ľ. ~sSCjTRA C£
důkaz. Podle předchozího Lemmatu je       rrlj)^ f*3 ^        1 f/, j
(l+aPr'-Sl+Vf  (modp«),/W/> ^It^ ^
a uvážíme-li tuto kongruenci modulo pz, dostaneme (1 + ap)pl 1 = 1       ^/-^ £ -/Jí> kH       ^= (mod př). Přitom přímo z předchozího Lemmatu a faktu p \ a plyne   -    .     ^ '
(1 + ap)pi 2 ^ 1 (mod pz), což dává požadované. □ ^
l^M/'1    fc-2 , ,
if       • ItÁÁ       tvrzení 4.2. Buď p liché prvočíslo. Pak pro každé l g n existuje f\ •> Aj^ Ij-
'     P-'     "1 ' primitivní kořen modulo pl.   .  ■ i    ,/  / „__      i 'i /■č-
() C/€-2       /^í důkaz. Necht g je primitivní kořen modulo p. Ukážeme, že pokud ~3
fo^Q/bf  ~ fy-W   ty Jjf1 ^ 1 ("m°d P2), je (? dokonce primitivním kořenem modulo pl pro <f ^ ^JjT-' libovolné / g n. (Pokud by platilo gp~1 = 1 (mod p2), pak (<7 + p)p_1 = <?^"*^, /j> fl*/*"2
yi   bSis^ft 1 + (p—l)gp~2p ^ 1 (mod p2), a tedy místo g můžeme volit za původní O A7
v) .   primitivní kořen číslo g + p.) *"= oCf) i> ti^<
Q^p"^ - Q ( T$J íl?     Nechť tedy g splňuje g^-1 ^ 1 (mod p2). Pak existuje a g Z, p { a   .--/-—-——•
"/ ' \ tak, že gp~x = 1 + p • a. Ukážeme, že g je modulo pl řádu (/?(pz) =  ^flřft. ^^"í/ ; 5^ c: OCp)  Li    (p ~        1 - Buď n g n nejmenši^číslo, splňující gn = 1 (modpz). A (f>)
v     Podle předchozího Lemmatu }e/gp~}/= 1 + p • a řádu/pz_yhiodulo pz. "
Pak ale
p* tf)
= (9")',1*=.|'^mod p') =" p''1 I ^  Zároveň z qn = 1 (mod p) plyne p —^1 | n. Protože jsou čísla p — 1 a
pz_1 nesoudělná, dostáváme (p— l)pz_1 | n. Proto n = (p(pl) a g je tedy
primitivní kořen modulo pz. □
tvrzení 4.3. Bud' p liché prvočíslo a g primitivní kořen modulo pl pro l g n. Pak liché z čísel g,g + pz je primitivním kořenem modulo 2pz.
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.
/. ty
S'JtfH' Lemma. Buď1 G N, / > 3. Pak 52' 3 = 1 + 21'1 (mod 2ř).
důkaz. Obdobně jako výše pro 2 \ p. □ ^ Lemma. Buď l G N, / > 3. Pak řád čísla 5 modulo 2l je 2l~2. (f/é)~ S
DŮKAZ. Snadný z předchozího Lemmatu.
Tvrzení 4.4. Nectí , e N. ft™*™,, toftn, .„oA.fo 2' UftT,
právě tehdy, když l < 2. ^^fj   ^  ^ ^
, a. ^,1,    DŮKAZ. Buď / > 3. Pak množina r'Uŕ y t-   ^— ?
mIV/mJ^      s = {(_-1)..5%e{0,1},o<i<2.-»;4ez} M;
fll K tvoří redukovanou soustavu zbytků modulo 2Z (má totiž </?(2z) prvků
^-^]] * r\J ' o kterých se snadno ukáže, že isou do dvou nekongruentní modulo 2^.
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) = 2Z~1. □
rb. (/nad2^)
«    — «    t Posledním kamínkem do mozaiky tvrzení, která společně dokazují
\      /    /  i-f~í) Větu 30, je tvrzení popisující neexistenci primitivních kořenů pro složená kjSOi (Iwl ) čísla, která nejsou mocninou prvočísla (ani jejím dvojnásobkem).
TVRZENÍ 4.5. Nechť 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. Ýy- Yi\"
flT     k f n rí >J\ DŮKAZ. Buď rozklad m na prvočísla tvaru 2ap^1 ■■■p^k, kde a G (0[Jfŕ)~~(/?f2}Lflľ)
ÍA  - 1 l^*^   /    N0, cti G N, 2 f pí a buď platí fc > 2 nebo fc > 1 a a > 2. Označíme-        * \ ,
li ô = [v9(2a),v9(p^),...,v9(p|^]7^ák se snadno vidí, že ô < ^(2a) ■  O ~[f(Í) iLflťjj?]
1      f-/it *>) ^(Pi1)"""^^!^ = ^(m) a že pro libovolné a G Z, (a,m) = 1 platí \ňiár\- i
Ol s^(tŕ\     &   'p/j--flá = 1 (mod m). Proto modulo m neexistují primitivní kořeny.       □ ^ř^J y— g
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.
tj 48
*»        1 věta 31. -Bnď m takové, že modulo m existují primitivní kořeny.
I\ Zapišme ip(rri) = g"1 • • • q^k. Pak pro libovolné g E 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(rn).
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 E {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).
^ pl p
= 10^(mod 41
= 812 = (-1)2 = 1   (mod 41)
= 1 (mod 41 á Jitu/ k.
vždy dělí řád 2 oUt^if^d h p  —í = £ '    / b# ?~
íl6
4\10
(28)2 = 10'
40       /O20\2 _
= 18   (mod 41) 1   (mod 41) j> i-
24U = (2 = 10   (mod 41)
(38)2 -34 = 1 • 1 • (-1) = -1   (mod 41)
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)
Pak6- = 2-.3'S(6.41 + 10)(-4.41 + l)S „SMfaV) = -34-41 + 10 = 7.-41 + 10   (mod 412) ,j   ' '
^-(68)5 = (7 - 41 + 10)5 = (105 + 5 - 7 - 41-104)=   7^.^^ /fyZJ = 104(10 + 35 • 41) = (-2 • 41 - 4)(-6 • 41 + 10) = = (4-41 -40) =(jS~p^) (mod412).
-€> * / f»k, tAotf wl
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).^ss- C^-^^ JILň^j
$4 4.6. Kvadratické kongruence a Legendreůy symbol. Naším
" IV'*     r> rvvaaraticKe Kongruence a i^egenareuy symDoi. iNasím
P       I ť úkolem bude najít jednodušší podmínku, jak zjistit, jestli je řešitelná J7 jfaj^ '/^(^
■?  i    „ I. "\ (a případně, kolik má řešení) kvadratická kongruence ' J
' arr + o:r + c = 0   (mod m).
Z obecné teorie, uvedené v předchozích odstavcích, je snadné vidět, r  )    r*~T)( D^1) ^e ^ roznodnutí, je-li tato kongruence řešitelná, stačí určit, je-li řešitelná (X*L ííMLs   ^(ly (binomická) kongruence
HřWírf x2 = a   (modp), (27)
^ 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 líd^ čť^lwkvadratickém případě snažíme najít kritérium jednodušší na výpočet.
)C"^Sm* ^^pŘÍKLAD. Určete počet řešení kongruence x2 = 219 (mod 383).
/ j^l /\ i \ Řešení. Protože 383 je prvočíslo a (2, (^(383)) = 2, z Věty 27 plyne, C&j'    J1"* fj 'ze daná kongruence je řešitelná (a má 2 řešení), právě tehdy, když
KojČoM d 219~ = 219191 = 1 (mod 383)- 0
věření platnosti není bez použití tij 1    Hs'Pj. )   výpočetní techniky snadné (i když je to pořád ještě „na papíře" vyčíslitelné). (_SCi'Ä f/    Závěrem této části tuto podmínku ověříme s pomocí Legendreova sym-
£     /I /   1        bolu daleko snadněji.
(I 1 Definice. Nechť je p liché prvočíslo. Legendreův symbol definujeme
-fo u' ŕtftó*/        Předpisem ] /\ ví       í II       r> I /i,, n. ie kvadratickv zbvtek mnHnln r>. «■ í ffo /
/\>l      * II     pf a, a je kvadratický zbytek modulo p, 3<£3 /
Jí í\ - a I)     v)= 10 p 1 a'
p) y~ 1   p f a, a je kvadratický nezbytek modulo p. fj^-^^í