38
Z druhé kongruence dostáváme, že x = —3 + 81í, kde ŕ G Z. Dosazením do třetí kongruence soustavy (23) dostaneme
-3 + 81í = -4 (modli),
tedy 81* = — 1 (mod 11), tj. 4r = 32 (mod 11), odkud t = 8 (mod 11), a proto t = —3 + lis, kde s G Z. Dosazením x = —3 + 81(—3 + lis) = —3 — 3 • 81 + 11 • 81s do první kongruence soustavy (23) dostaneme
-3-3-81 + ll-81s = 3   (mod 4),
tedy
1 + 1 • 1 + (-1) • ls = 3   (mod 4), tj. —s = 1 (mod 4) a proto s = —1 + 4r, kde r G Z. Je tedy
x = -3-3-81 + ll-81(-l+4r) = -3-14-81+4-ll-81r = -1137+3564r,
neboli x = —1137 (mod 3564), což je také řešení zadané kongruence.
□
4.3. Kongruence vyšších stupňů. Vraťme se k obecnějšímu případu, kdy na obou stranách kongruence stojí mnohočleny téže proměnné x s celočíselnými koeficienty. Snadno můžeme tuto kongruenci odečtením upravit na tvar
F(x) = 0   (mod m), (24)
kde F(x) je mnohočlen s celočíselnými koeficienty a m G N. Věta 20 nám poskytuje sice pracnou, ale univerzální metodu řešení této kongruence. Při řešení kongruence (24) totiž stačí zjistit, pro která celá čísla a, 0 < a < m, platí F (a) = 0 (mod m). Nevýhodou této metody je její pracnost, která se zvyšuje se zvětšující se hodnotou m. Je-li m složené, m = p"1 ... p^k, kde p±, ..., pk jsou různá prvočísla, a je-li navíc k > 1, můžeme nahradit kongruenci (24) soustavou kongruenci
F(x)=0 (modp™1)
i (25) F(x) = 0   (mod plh),
která má stejnou množinu řešení, a řešit každou kongruenci této soustavy zvlášť. Tím získáme obecně několik soustav kongruenci (19), které už umíme řešit. Výhoda této metody spočívá v tom, že moduly kongruenci soustavy (25) jsou menší než modul původní kongruence (24).
příklad. Řešte kongruenci x5 + 1 = 0 (mod 11).
39
Řešení. Označme F (x) = x5 + 1. Pak platí F(0) = 1, F(l) = 2 a dále platí
F(2) = 33 = 0 (modli),
F (3) = 35+ 1= 9- 9- 3 + 1 = (-2)2 - 3 + 1 = 12 + 1 = 2 (mod 11), F(4) = 45 + 1 = 210 + 1 = 1 + 1 = 2 (modli),
kde jsme využili Fermatovu větu 16, podle které 210 = 1 (mod 11). Podobně dále
F(5) =	55 +	1	=  165 + 1 :	= 410 + 1	= 1 + 1 = 2 (modli),
F(6) =	65 +	1	= (-5)5 +	1 = -165	+ 1 = -410 + 1 = 0 (modli
F(7) =	75 +	1	= (-4)5 +	1 = -210	+ 1 =-1 + 1 = 0 (modli),
F(8) =	85 +	1	_ 25 . 210 H	h 1 = 32 -f	-1 = 0   (mod 11),
F(9) =	95 +	1	= 310 + 1 E	= 1 + 1 =	2   (mod 11),
F(10) =	= 105	+	1 = (-1)5	+ 1 = 0	(mod 11),
a tedy řešením kongruence + 1 = 0 (mod 11) jsou právě všechna x, vyhovující některé z kongruencí x = 2 (mod 11), rr = 6 (mod 11), x = 7 (mod 11), x = 8 (mod 11), rr = 10 (mod 11). □
příklad. Řešte kongruenci x3 — 3x + 5 = 0 (mod 105).
řešení. Kdybychom postupovali obdobně jako dříve pro m = 105, museli bychom spočítat pro F{x) = x3 — 3x + 5 sto pět hodnot -F(O), F(l), ..., F(104). Proto raději rozložíme 105 = 3 • 5 • 7 a budeme řešit kongruence F{x) = 0 postupně pro moduly 3, 5, 7. Platí F(0) = 5, F(l) = 3, F(2) = 7, F(3) = 23, F(-l) = 7, F{-2) = 3, F(-3) = -13 (pro snadnější výpočty jsme počítali například F(—l) místo F(6) -využijeme toho, že F(6) = F(—l) (mod 7) podle předchozího Tvrzení a podobně). Kongruence F{x) = 0 (mod 3) má tedy řešení x = 1 (mod 3); kongruence F(x) = 0 (mod 5) má řešení rr = 0 (mod 5); řešením kongruence F{x) = 0 (mod 7) jsou x G Z splňující rr = 2 (mod 7) nebo x = — 1 (mod 7). Zbývá tedy vyřešit dvě soustavy kongruencí:
x = 1   (mod 3), x =   1   (mod 3),
x = 0 (mod 5), a x = 0 (mod 5), x = 2   (mod 7) x = — 1   (mod 7).
Protože první dvě kongruence jsou u obou soustav stejné, budeme se nejprve zabývat jimi. Ze druhé kongruence dostáváme x = 5t pro í G Z, dosazením do první
5í = 1   (mod 3),
40
tedy — t = 1 (mod 3), odkud t = — 1 + 3s pro s G Z, odkud x = —5 + 15s. Dosaďme nejprve do třetí kongruence první soustavy:
-5 + 15s = 2   (mod 7),
odkud s = 0 (mod 7), tj. s = 7r pro r G Z a proto x = —5 + 105r. Dosadím e-li x = — 5 + 15s do třetí kongruence druhé soustavy, dostaneme
—5 + 15s = —1   (mod 7),
odkud s = 4 (mod 7), tj. s = 4 + 7r pro r G Z, a proto x = —5 + 15(4 + 7r) = 55 + 105r. Celkem jsou tedy řešením dané kongruence F(x) = 0 (mod 105) všechna celá čísla x, splňující x = —5 (mod 105) nebo x = 55 (mod 105). □
Postup pro řešení kongruencí, kde modulem je mocnina prvočísla, udává důkaz následující věty.
VĚTA 24 (Henselovo lemma). Nechť p je prvočíslo, f(x) G 1*[x], a G Z je takové, že p | f (a),p \ f (a). Pak platí: pro každé n G N má soustava
x = a   (mod p) f(x) = 0   (mod pn) ^ právě jedno řešeni modulo pn.
DŮKAZ. Indukcí vzhledem k n. Případ n = 1 je zřejmý. Nechť dále n > 1 a věta platí pro n — 1. Je-li x řešením (26) pro n, je řešením (26) i pro n—1. Libovolné řešení (26) pro n je tedy tvaru
x = cn_! + k ■ pn_1,   kde A; G Z.
Je třeba zjistit, zda /(cn_i + k ■ pn~ľ) = 0 (mod pn). Víme, že pn_1 | /(cn-i + & ' pn_1) a užijme binomickou větu pro f(x) = amxm + • • • + a\X + a0, kde a0) • • • > am £ Z. Pak
(cn_x + k ■ p™'1)1 = én_x + i ■ é-\ ■ kpn-x   (mod pn).
Platí tedy
f(Cn^ + fc -p"-1) = f(cn^) + k-p^fic^),
tj-
/(c^x + fc • p""1) = 0   (mod pn) ^
^O^l^A + k-fic^) (modp).
Protože cn_! = a (modp), dostaneme /'(cn_i) = /'(a) ^ 0 (modp), tedy (/'(cn_i),p) = 1. Užitím Věty 21 o řešitelnosti lineárních kongruencí dostáváme, že existuje právě jedno řešení k (modulo p) této kongruence a protože cn_! bylo podle indukčního předpokladu jediné řešení modulo pn_1, je číslo cn_i + A;-pn_1 jediným řešením (26) modulo pn. □
41
PŘÍKLAD. Řešte kongruenci x4 + 7x + 4 = 0 (mod 27).
ŘEŠENÍ. Řešme nejprve tuto kongruenci modulo 3 (např. dosazením) - snadno zjistíme, že řešení je x = 1 (mod 3). Zapišme řešení ve tvaru x = 1 + 3t, kde ŕ G Z a řešme kongruenci modulo 9.
x4 + 7x + 4 = 0   (mod 9)
(l + 3ť)4 + 7(l + 3ť)+4 = 0   (mod 9)
l+4-3ŕ + 7 + 7-3ŕ + 4 = 0   (mod 9)
33í = —12   (mod 9)
lir = -4   (mod 3)
t = 1   (mod 3)
Zapsáním t = 1 + 3s, kde s G Z dostaneme x = 4 + 9s a po dosazení (4 + 9s)4 + 7(4 + 9s) + 4 = 0   (mod 27) 44 + 4 • 43 • 9s + 28 + 63s + 4 = 0   (mod 27) 256 • 9s + 63s = -288   (mod 27) 256s + 7 s = -32   (mod 3) 2s = 1   (mod 3) s = 2   (mod 3)
Celkem dostáváme řešení x = 4 + 9s = 4 + 9(2 + 3r) = 22 + 27r, kde r G Z, neboli x = 22 (mod 27). □
Řešení obecných kongruenci vyššího stupně jsme tedy převedli na řešení kongruenci modulo prvočíslo. Ukazuje se, že zde je největší „kámen úrazu", protože pro tyto kongruence žádný obecný postup (s výjimkou postupu podle Věty 20, tj. vyzkoušení všech možností) není znám. Uvedeme alespoň několik obecných tvrzení ohledně řešitelnosti a počtu řešení takových kongruenci a v dalších částech skript podrobnější výsledky v některých speciálních případech.
4.4. Kongruence s prvočíselným modulem.
VĚTA 25. Buď p prvočíslo, f(x) G 7L\x\. Libovolná kongruence j(x) = 0 (mod p) je ekvivalentní s kongruenci stupně nejvýše p — 1.
DŮKAZ. Protože pro libovolné a G Z platí p \ ď — a (důsledek Malé Fermatovy věty), jsou řešením kongruence xp — x = 0 (mod p) všechna celá čísla. Vydělíme-li polynom f(x) se zbytkem polynomem xp — x, dostaneme
f(x) = q(x) ■ (xp — x) + r(x) pro vhodné f(x),r(x) G Z, kde stupeň r{x) je menší než stupeň dělitele tedy než p. Dostáváme tak, že kongruence r{x) = 0 (mod p) je ekvivalentní kongruenci f(x) = 0 (mod p) a je přitom stupně nejvýše p-1. □
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.