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 + 11 • 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
y^l/Qyjji. 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)^-^   FGl) lOÍ^^fyt)^)^
i (25) F(x)=0   (modp^), <n.^     - - .
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 +	-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 x5 + 1 = 0 (mod 11) jsou právě všechna vyhovující některé z kongruencí rr = 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í x = 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
mo if)
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. Do-sadíme-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 [/[ují^Hr) ■        V^a^: Pro každé n G N má
SÄ     f*^)       x^a   (mod p) «t*tpj4k Xo
/(*)
právě jedno řešení 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 r^- 1. Je-li x řešením (26) pro n, je řešením (26) y     i pro n — 1. LibojjtflíTe řeŠéití (26) pro n je tedy tvaru
x = cn_1 + A;-pn-1,   kde k G Z.
Je třeba zjistit, zda /(cn_i + A; • pn_1) = 0 (mod pn). Víme, že pn_1 | a užijme binomickou větu pro f(x) = amxm + • •
11. \ v
-n—ľ*
(cn_i + A;
am G Z. Pak
Platí tedy
p
n—1\
ftCn-j + k-p"-1/'^),^ '
p
k-
/(cn_i + k
0   (mod p" 0 =
roubit ^
p
,n—1
(mod p).
/(cn_i + A;
Protože cn_! = a (mod p), dostaneme /'(cn_i) = /'(a) ^ 0 (mod p), HxO ' ^     . \
tedy (/'(cn_i),p) = 1. Užitím Věty 21 o řešitelnosti lineárních kon- _ / z / /fyj'j^" jij
gruencí 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é y ď t^t)
řešení modulo pn_1, je číslo cn_i + k-p"1^1 jediným řešením (26) modulo ■Kyj —   r-'
Pn.                                                          n ý &h)
sp«, f J b   * j- y* **> - * ^
/Vo1* rf+l .1,1
ve tvaru x
5"
PŘÍKLAD. Řešte kongruenci     + 7x + 4 = 0 (mod 27).
ŘEŠENÍ. Řešme nejprve tuto kongruenci modulo 3/(napr. vdosa-zením) - snadno zjistíme, že řešení je x = 1 (mod 3).napišme řešení £
3í, kde ŕ G Z a řešme kongruenci modulo 9. x4 + 7x + 4 = 0   (mod 9 7(1 + 3ť) +4 = 0 7 + 7- 3í + 4 = 0 33r = -12 lir = -4 ŕ = 1
saflV *«v
Zapsáním ŕ = 1 + 3s, kde s G Z dostaneme x
(mod 9 (mod 9 (mod 9 (mod 3 (mod 3
= 4 + 9s a po dosazení
Celkem dostáváme řešení x = 4 kde r G Z, neboli x = 22 (mod 27).
m*3'
22
27r, □
Ř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 f(x) = 0 (mod p) je ekvivalentní s kongruenci stupně nejvýše p — 1.
DŮKAZ. Protože pro libovolné a G Z platí p \ Fermatovy věty), jsou řešením kongruence xp — x
' — a (důsledek Malé 0 (mod p) všechna
celá čísla. Vydělíme-li polynom f(x) se zbytkem polynomem x'p dostaneme £ fa J ^ )r( 9}    (•*<*}{ pj
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. □
k*w*o ty     4 . 6 .
s VĚTA 26. -Bnd p prvočíslo, f{x) g 7h\x\. Má-lí kongruence f{x) = O ^J — v/
fo\ fy V$L/d (mod p) více nežst(f) řešeni, pak jsou všechny koeficienty polynomu f £.
*   , >i   řrC\ násobkem p.
\ / DŮKAZ. V jazyce algebry jde vlastně o počet kořenů nenulového (_ÍLfc"*-        * /
1)l< S>fDf&h\ polynomu nad (konečným) tělesem Zp, kterých je nejvýše st(/).      □ ^J^^JJ Q^)(^)j
"v"  '    1/    'CWlí ) důsledek. (Jiný důkaz Wilsonovy věty) Pro každé prvočíslo p
&L-fcrfl/ (p-l)! = -l   (mod p).
DŮKAZ. Pro p = 2 je tvrzení zřejmé, dále uvažujme jen lichá
" prvočísla p. Řešeném, kongruence l^tilh^^ti) (x_i)(x*2)---(a;-(p-l))-(ž^-l) = 0 (modp)
je podle Malé Fermatovy věty libovolné a g Z, které není násobkem
/.fó)" (£~%iflty$vfaj V-, tj- kongruence má p — 1 řešení. Přitom je ale její stupeň menší než í . a - \ (J\ (*JÍV~ ^' Pro^° Jsou podle předchozí věty všechny koeficienty polynomu na j/i-^J— 1 ' *^f4evé straně kongruence násobkem p, speciálně absolutní člen, kterým je
Lt-^     í« ; t (tXzsfliikl (p — 1)! + 1. Tím je Wilsonova věta dokázána. x   , □
ífivffl ^ ^   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
^ "V C0/ 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
^ qj C      J\ můžeme omezit na případ, kdy je a nesoudělné s modulem kongruence
Éf       . ~~ v opačném případě totiž vždy můžeme pomocí ekvivalentních úprav
V\ íwTC*-Š kongruencí na tento případ převést nebo rozhodnout, že kongruence
-jjO / není řešitelná.
příklad. Řešte kongruencí
x = 18   (mod 63).
Řešení. Protože je (18,63) = 9, musí platit 9 | x2, tj. 3 | x. v . * Položíme-li x = 3x1} X\ g Z, dostáváme ekvivalentní kongruencí x\ = 2
fito, l^r^ f       (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 x — 3 * x~y. dostáváme kongruencí
27a:? = 3   (mod 18),
která zřejmě nemá řešení, protože (27,18) \ 3.