32
4.1. Lineární kongruence o jedné neznámé.
VĚTA 21. Nechť m G N, a, b G Z. Označme d = (a, m). Pak kongruence
ax = b   (mod m)
(o jedné neznámé x) má řešeni pravé tehdy, když d | b.
V případe, kdy d | b, má tato kongruence pravé d řešeni (modulo
m).
DŮKAZ. Dokážeme nejprve, že uvedená podmínka je nutná. Je-li celé číslo c řešením této kongruence, pak nutně m \ a ■ c — b. Pokud přitom d = (a, m), pak protože d \ m i d \ a-c—b a d | a-c— (a-c—b) = b.
Obráceně dokážeme, že pokud d | b, pak má daná kongruence právě d řešení modulo m. Označme a1; bľ G Z a ni\ G N tak, že a = d- a1? b = d -bi a m = d-ni\. Řešená kongruence je tedy ekvivalentní s kongruencí
a\ ■ x = bi   (mod mi),
kde (a1;mi) = 1. Tuto kongruenci můžeme vynásobit číslem a^-mi"> 1 a díky Eulerově větě obdržíme
x = bi ■ a^-mi"> 1   (mod nii).
Tato kongruence má jediné řešení modulo ni\ a tedy d = mjni\ řešení modulo m. □
Následující příklad ukáže, že postup uvedený v důkazu věty obvykle není tím nej efektivnějším - s výhodou lze použít jak Bezoutovu větu, tak ekvivalentní úpravy řešené kongruence.
PŘÍKLAD. Řešte 39x = 41 (mod 47)
řešení.        (1) Nejprve využijeme Eulerovu větu. Protože (39,47) = 1, platí
39^(47) = 3946 _ x   (mod 47);
tj-
39^39:r = 3945 • 41   (mod 47),
3946=1
z čehož už dostáváme
x = 3945 - 41   (mod 47).
Úplné řešení vyžaduje ještě vypočtení zbytku po dělení čísla 3945 • 41 číslem 47, ale to již jistě laskavý čtenář zvládne sám a zjistí výsledek x = 36 (mod 47)
33
(2) Další možností je využít Bezoutovu větu. Euklidovým algoritmem pro vypočtení (39,47) dostáváme
47 = 1 • 39 + 8
39 = 4 • 8 + 7
8 = 1-7+1
Z čehož zpětným odvozením dostáváme
1=8-7 = 8-(39 - 4-8) = 5- 8- 39 =
= 5 • (47 - 39) - 39 = 5 • 47 - 6 • 39.
Uvážíme-li tuto rovnost modulo 47, dostaneme
1 = -6 • 39   (mod 47)   / • 41
41 = 41 • (-6) -39   (mod 47)   / • 41
x = 41 • (-6)   (mod 47) x = -246   (mod 47) x = 36   (mod 47)
(3) Obvykle nej rychlejším, ale nejhůře algoritmizovatelným způsobem řešení je metoda takových úprav kongruence, které zachovávají množinu řešení.
39x = 41   (mod 47) —8x = —6   (mod 47) Ax = 3   (mod 47) Ax = -44   (mod 47) x = —11   (mod 47) x = 36   (mod 47)
□
Pomocí věty o řešitelnosti lineárních kongruencí lze dokázat mj. významnou Wilsonovu větu udávající nutnou (i postačující) podmínku prvočíselnosti. Takové podmínky jsou velmi významné ve výpočetní teorii čísel, kdy je třeba efektivně poznat, je-li dané velké číslo prvočíslem. Bohužel dosud není známo, jak rychle vypočítat modulární faktoriál velkého čísla, proto není v praxi Wilsonova věta k tomuto účelu používána.
VĚTA 22 (Wilsonova). Přirozené číslo n > 1 je prvočíslo, právě když
(n - 1)! = -1   (mod n) (18)
DŮKAZ. Dokážeme nejprve, že pro libovolné složené číslo n > 4 platí n \ (n — 1)!, tj. (n — 1)! = 0 (mod n). Nechť 1 < d < n je netriviální dělitel n. Je-li d ^ n/d, pak protože 1 < d,n/d < n — 1,
34
je n = d ■ n/d \ {n — 1)!. Pokud d = n/d, tj. n = d2, pak protože je n > 4, je i d > 2 a n | {d ■ 2d) | (n — 1)!. Pro n = 4 snadno dostáváme (4- 1)! = 2 ^ -1 (mod 4).
Nechť je nyní p prvočíslo. Čísla z množiny {2,3,..., p—2} seskupíme do dvojic vzájemně inverzních čísel modulo p, resp. dvojic čísel, jejichž součin dává zbytek 1 po dělení p. Pro dané číslo a z této množiny existuje podle předchozí věty jediné řešení kongruence a ■ x = 1 (mod p). Protože a ^ 0,1, p — 1, je zřejmé, že rovněž pro řešení c této kongruence platí c ^ 0,1, —1 (mod p). Číslo a nemůže být ve dvojici samo se sebou; kdyby totiž a ■ a = 1 (mod p), pak nutně a = ±1 (mod p). Součin všech čísel uvedené množiny je tedy tvořen součinem (p — 3)/2 dvojic (jejichž součin je vždy kongruentní s 1 modulo p). Proto je
(p- 1)! = l(P-3)/2 ■ (p- 1) = -1   (mod p).
□
4.2. Soustavy lineárních kongruencí o jedné neznámé. Máme-li soustavu lineárních kongruencí o téže neznámé, můžeme podle Věty 21 rozhodnout o řešitelnosti každé z nich. V případě, kdy aspoň jedna z kongruencí nemá řešení, nemá řešení ani celá soustava. Naopak, jestliže každá z kongruencí řešení má, upravíme ji do tvaru rr = q (mod m,/). Dostaneme tak soustavu kongruencí
x = Ci   (mod mi)
i (19) x = Ck   (mod nik)
Zkoumejme nejprve případ k = 2, který - jak uvidíme později - má stěžejní význam pro řešení soustavy (19) s k > 2.
VĚTA 23. Nechi Ci,c2 jsou celá čísla, nii,ni2 přirozená. Označme d = (nii,ni2). Soustava dvou kongruencí
x = ci (mod mi) x = c2   (mod ni2)
v případě Ci ^ c2 (mod d) nemá řešení. Jestliže naopak cx = c2 (mod d), pak existuje celé číslo c tak, že x G Z splňuje soustavu (19), právě když vyhovuje kongruencí
x = c   (mod [m1,m2]).
DŮKAZ. Má-li soustava (20) nějaké řešení x G Z, platí nutně x = cľ (mod d), x = c2 (mod d), a tedy i C\ = c2 (mod d). Odtud plyne, že v případě Ci ^ c2 (mod d) soustava (20) nemůže mít řešení.
Předpokládejme dále Ci = c2 (mod d). První kongruencí soustavy (20) vyhovují všechna celá čísla x tvaru x = Ci + tmi, kde ŕ G Z je
35
libovolné. Toto x bude vyhovovat i druhé kongruenci soustavy (20), právě když bude platit c\ + tni\ = c2 (mod 1112), tj.
tmi = C2 — Ci   (mod m2).
Podle Věty 21 má tato kongruence (vzhledem k ť) řešení, neboť d = (7711,7712) dělí C2 — Ci, a t G Z splňuje tuto kongruenci právě když
tj. právě když
^ C2-C1     /TTliy^M / 7712 X
C2 - Ci     /mAří-H 77l2
kde r G Z je libovolné. Dosazením
/fflAW-)        77li77l2 r ,
X = Ci +ÍÍ711 = Ci + (C2 - Ci) • y—^j +r-^-      = C + r • [77li,77l2J,
kde c = Ci + (c2 — Ci) • [nii/d)^m2/d\ neboť 77ii77i2 = d ■ [77ii,77i2]. Našli jsme tedy takové c G Z, že libovolné x G Z splňuje soustavu (20), právě když
x = c   (mod [7711,77i2]), což jsme chtěli dokázat. □
Všimněme si, že důkaz této věty je konstruktivní, tj. udává vzorec, jak číslo c najít. Věta 23 nám tedy dává metodu, jak pomocí jediné kongruence zachytit podmínku, že x vyhovuje soustavě (20). Podstatné je, že tato nová kongruence je téhož tvaru jako obě původní. Můžeme proto tuto metodu aplikovat i na soustavu (19) - nejprve z první a druhé kongruence vytvoříme kongruenci jedinou, které vyhovují právě ta x, která vyhovovala původním dvěma kongruencím, pak z nově vzniklé a z třetí kongruence vytvoříme další atd. Při každém kroku se nám počet kongruenci soustavy sníží o 1, po k — 1 krocích tedy dostaneme kongruenci jedinou, která nám bude popisovat všechna řešení soustavy (19). Poznamenejme ještě, že číslo c z Věty 23 není nutné určovat pomocí uvedeného vzorce. Můžeme vzít libovolné ŕ G Z vyhovující kongruenci
77li       C2 - Ci   / 77l2 \
a položit c = Ci + tmi.
DŮSLEDEK (Čínská zbytková věta). Nechť mľ,,... ,771^ G N jsou po dvou nesoudělná, a1;...,     G Z. Pak platí: soustava
X = CLi     (mod 77li)
; (21)
X = CLk     (mod 77lfc)
má jediné řešeni modulo mi ■ m2 • • • m^.
36
PŘÍKLAD. Řešte systém kongruencí
x = —3   (mod 49) x =   2   (mod 11).
řešení. První kongruencí splňují právě všechna celá čísla x tvaru x = —3 + 49í, kde ígZ. Dosazením do druhé kongruence dostáváme
-3 + 49í = 2 (modli),
odkud
5í = 5   (mod 11), tedy, vzhledem k (5,11) = 1, po vydělení pěti
t = 1   (mod 11),
neboli t = 1 + lls pro libovolné s G Z. Proto x = —3+49(l + lls) = 46+ 539s, kde s G Z, což můžeme také zapsat jako x = 46 (mod 539). □
PŘÍKLAD. Řešte systém kongruencí
x = 1 (mod 10) x = 5 (mod 18) x = —4   (mod 25).
řešení. Z první kongruence dostáváme x = 1 + lOí pro í g Z. Dosazením do druhé kongruence získáme
1 + 10* = 5   (mod 18),
tedy lOí = 4 (mod 18). Protože (10,18) = 2 dělí číslo 4, má tato kongruence podle věty 4.2 řešení t = 2 • 55 (mod 9), přičemž 2 • 55 = 10-252 = l-(-2)2 = 4 (mod 9), a tedy t = 4+9s, kde s G Z. Dosazením x = 1 + 10(4 + 9s) = 41 + 90s. Z třetí kongruence pak vychází
41 + 90s = -4   (mod 25),
tedy 90s = —45 (mod 25). Vydělením pěti (včetně modulu, neboť 5 | 25)
18s = -9   (mod 5),
odkud — 2s = 1 (mod 5), tedy 2s = 4 (mod 5), s = 2 (mod 5), a proto s = 2 + 5r, kde r G Z. Dosazením rr = 41 + 90(2 + 5r) = 221 + 450r, tedy x = 221 (mod 450). □
PŘÍKLAD. Řešte systém kongruencí
x = 18 (mod 25) x = 21 (mod 45) x = 25   (mod 73).
37
řešení. Z první kongruence x = 18 + 25í, kde ŕ g Z. Dosazením do druhé kongruence
18 + 25t = 21 (mod45),
tedy
25t = 3   (mod 45).
Tato kongruence však podle Věty 21 nemá řešení, neboť (25,45) = 5 nedělí číslo 3. Proto nemá řešení ani celý systém. Tento výsledek bychom také dostali přímo z Věty 23, neboť 18 ^ 21 (mod (25,45)).
□
PŘÍKLAD. Řešte kongruenci 23 941x = 915 (mod 3564).
řešení. Rozložme 3564 = 22 • 34 • 11. Protože ani 2, ani 3, ani 11 nedělí číslo 23 941, platí (23 941,3564) = 1 a tedy podle Věty 23 má kongruence řešení. Protože (^(3564) = 2 • (33 • 2) • 10 = 1080, je řešení tvaru x = 915 • 23 9411079 (mod 3564). Úprava čísla stojícího na pravé straně by však vyžádala značné úsilí. Proto budeme kongruenci řešit poněkud jinak. Podle Věty 13 (6) je x g Z řešením dané kongruence právě když je řešením soustavy
23941a; = 915   (mod 22)
23941a; = 915   (mod 34) (22) 23941a; = 915   (mod 11)
Vyřešíme nyní každou z kongruenci soustavy (22) zvlášť. První z nich je splněna, právě když
x = 3   (mod 4),
druhá, právě když
A6x = 24   (mod 81),
odkud vynásobením dvěma 92x = 48 (mod 81), tj. llx = —33 (mod 81) a po vydělení jedenácti
x = —3 (mod 81). Třetí kongruence je splněna, právě když
5x = 2 (mod 11), odkud vynásobením číslem —2 dostaneme — lOx = —4 (mod 11), tedy
x = —4   (mod 11).
Libovolné x g Z je tedy řešením soustavy (22), právě když je řešením soustavy
x =   3   (mod 4)
x = -3   (mod 81) (23) x = —4   (mod 11)
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).