42
věta 26. Bud' p prvočíslo, f (x) G 7L\x\. Má-li kongruence f (x) = O (mod p) více než st(/) řešení, pak jsou všechny koeficienty polynomu f násobkem p.
důkaz. V jazyce algebry jde vlastně o počet kořenů nenulového polynomu nad (konečným) tělesem Zp, kterých je nejvýše st(/). □
důsledek. (Jiný důkaz Wilsonovy věty) Pro každé prvočíslo p platí
(p — 1)! = —1   (mod p).
důkaz. Pro p = 2 je tvrzení zřejmé, dále uvažujme jen lichá prvočísla p. Řešením kongruence
(x - l)(x - 2) • • • (x - (p - 1)) - (x^1 - 1) = 0   (mod p)
je podle Malé Fermatovy věty libovolné a G Z, které není násobkem p, tj. kongruence má p — 1 řešení. Přitom je ale její stupeň menší než p—l, proto jsou podle předchozí věty všechny koeficienty polynomu na levé straně kongruence násobkem p, speciálně absolutní člen, kterým je (p — 1)! + 1. Tím je Wilsonova věta dokázána. □
4.5. Binomické kongruence a primitivní kořeny. V této části se zaměříme na řešení speciálních typů polynomiálních kongruencí vyššího stupně, tzv. binomických kongruencí. Jde o analogii binomických rovnic, kdy polynomem f(x) je dvojčlen xn — a. Snadno se ukáže, že se můžeme omezit na případ, kdy je a nesoudělné s modulem kongruence - v opačném případě totiž vždy můžeme pomocí ekvivalentních úprav kongruencí na tento případ převést nebo rozhodnout, že kongruence není řešitelná.
příklad. Řešte kongruencí
x2 = 18   (mod 63).
Řešení. Protože je (18,63) = 9, musí platit 9 | x2, tj. 3 | x. Položíme-li x = 3x1} X\ G Z, dostáváme ekvivalentní kongruencí x\ = 2 (mod 7), která již splňuje omezení na nesoudělnost modulu a pravé strany kongruence. Podle Věty 26 víme, že má nejvýše 2 řešení a snadno se vidí, že jimi jsou x\ = ±3 (mod 7), tj. x\ = ±3, ±10, ±17, ±24, ±31, ±38, ±45, ±52, ±59 (mod 63). Řešeními původní kongruence jsou tedy x = 3 • X\ (mod 63), tj. x = ±9, ±12, ±30 (mod 63).
příklad. Řešte kongruencí
x3 = 3   (mod 18).
řešení. Protože je (3,18) = 3, nutně 3 | x. Užijeme-li, podobně jako výše, substituci dostáváme kongruencí
27a:? = 3   (mod 18),
která zřejmě nemá řešení, protože (27,18) f 3.
43
Definice. Nechť m £ N, a £ Z, (a, m) = 1. Číslo a nazveme n-tým mocninným zbytkem modulo m, pokud je kongruence
xn = a   (mod m)
řešitelná. V opačném případě nazveme a n-tým mocninným nezbytkem modulo m.
Pro n = 2,3,4 používáme termíny kvadratický, kubický a bikvad-ratický zbytek, resp. nezbytek modulo m.
V tomto odstavci ukážeme, jakým způsobem řešit binomické kongruence modulo m, pokud modulo m existují tzv. primitivní kořeny.
Definice. Nechť m G N. Celé číslo a G Z, (a, m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven ip{m).
Lemma. Je-li g primitivní kořen modulo m, pak pro každé číslo a £ Z, (a, m) = 1 existuje jediné xa G Z, 0 < xa < (p(m) s vlastností gXa = a (mod m).
Funkce a —^ xa se nazývá diskrétní logaritmus, příp. index čísla x (vzhledem k danému m a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami
{a G Z; (a,m) = 1,0 < a < m} a {x G Z; 0 < x < (p(m)}.
DŮKAZ. Stačí ukázat tvrzení o bijekci a protože obě množiny mají stejný počet prvků, stačí dokázat injektivitu uvedeného zobrazení. Předpokládejme, že pro x, y G Z, 0 < x, y < ip(m) je gx = gy (mod m). Podle Věty 18 pak x = y (mod íp(m)), tj. x = y. □
Později ukážeme, že primitivní kořeny existují „dostatečně často" na to, aby následující věta řešila všechny potřebné případy.
VĚTA 27. Buď m G N takové, že modulo m existují primitivní kořeny. Dále nechť a G Z, (a, m) = 1. Pak kongruence
x11 = a   (mod m)
je řešitelná (tj. a je n-tý mocninný zbytek modulo m), pravé když
a<p(m)/d _ x   (mod m);
kde d = (n, ip(m)).
Přitom, je-li tato kongruence řešitelná, má pravé d řešení.
DŮKAZ. Nechť g je primitivní kořen modulo m. Pak podle předchozího Lemmatu existuje pro libovolné x nesoudělné s m jediné y G Z; 0 < y < ip(m) tak, že x = gy (mod m), podobně pro dané a existuje jediné b G Z; 0 < b < (p(m) tak, že a = gb (mod m). Řešená binomická kongruence je tedy po této substituci ekvivalentní s kongruencí
(gy)n = gb   (mod m)
44
a s využitím Věty 18 i s lineární kongruencí
n ■ y = b   (mod íp(m)).
Tato kongruence je řešitelná, právě když d = (n,íp(m)) \ b (a jeli řešitelná, pak má d řešení). Zbývá dokázat, že d \ b, právě když a<p(m)/d = 1 (mod my
Kongruence 1 = a^ld = gb^m)ld platí, právě když y?(m) \ b-^, a to platí právě když d \ b. □
důsledek. Za předpokladů předchozí věty, je-li navíc (n,íp(m)) = 1, má kongruence xn = a (mod m) vždy řešení, a to jediné. Jinými slovy, umocňování na n-tou (kde n je nesoudělné s </?(m)) je bijekce na množině Z^ invertibilních zbytkových tříd modulo m.
důkaz. Zřejmý. □
Následující věty nám dávají obecnou informaci o počtu řešení kongruencí podle modulu, kterým je mocnina prvočísla. Jde o speciální případy Henselova lemmatu pro případ binomických kongruencí.
věta 28. Buď p prvočíslo, a G Z, n G N,p \ a, p \ n. Je-li kongruence xn = a (mod p) řešitelná, je řešitelná i kongruence xn = a (mod pa) pro libovolné přirozené číslo a a má stejný počet řešení jako kongruence modulo p.
důkaz. Plyne z Henselova lemmatu pro kongruencí f(x) = 0 (mod p), kde f(x) = xn — a. Pak totiž f'(x) = n ■ xn~ľ a pokud b G Z splňuje f(b) = 0 (mod p), pak jistě p \ b, a proto p \ f'(b).
□
věta 29. Buď neN, a G Z, 2 \ a. Označme dále l G N0 největší takové, že 2l | n. Je-li kongruence xn = a (mod 22Z+1) řešitelná, je řešitelná i kongruence xn = a (mod 2a) pro libovolné a G N, a > 2/ + 1 a má stejný počet řešení jako kongruence modulo 22l+1.
důkaz. Prozatím neuveden. □
poznámka. Uvážíme-li v předchozí větě přirozené číslo n = 2 (mod 4), pak je / = 1. Pro liché a je kongruence xn = a (mod 8) řešitelná právě když je a = 1 (mod 8) (a má 4 řešení). Díky přechozí větě víme, že pro a = 1 (mod 8) má řešení libovolná kongruence tvaru xn = a (mod 2a) pro a > 3 a má 4 řešení.
V předchozích odstavcích jsme se zabývali řešitelností binomických kongruencí podle modulů, pro které existuje primitivní kořen. Ve zbytku této části se budeme zabývat tím, pro která čísla primitivní kořeny existují. Postupně dokážeme následující větu:
věta 30. Buď m G n, m > 1. Primitivní kořeny modulom existují právě tehdy, když m splňuje některou z následujících podmínek:
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).