28
příklad. Pro liché číslo m > 1 nalezněte zbytek po dělení čísla
2íp(m)-l číslem m>
řešení. Z Eulerovy věty plyne 2^m) = 1 = 1 + m = 2r (mod m)), kde r = je přirozené číslo, 0 < r < m. Podle 13 (3) platí 2^m)~1 = r (mod m), a tedy hledaný zbytek po dělení je r = ^4^. □
tvrzení 3.1. Je-li p prvočíslo, p = 3 (mod 4), paA; pro libovolná celá čísla a, b z kongruence a2 + b2 = 0 (mod p) plyne a = b = 0 (mod p).
DŮKAZ. Předpokládejme, že pro a, 6 G Z platí a2 + o2 = 0 (mod p). Jestliže p | a, platí a = 0 (mod p), proto o2 = 0 (mod p), tedy p | 62, odkud vzhledem k tomu, že p je prvočíslo, dostáváme p | 6, a proto a = b = 0 (mod p), což jsme chtěli dokázat.
Zbývá prošetřit případ, kdy a není dělitelné prvočíslem p. Odtud dostáváme, že p nedělí ani 6 (kdyby p | 6, dostali bychom p | a2). Vynásobíme-li obě strany kongruence a2 = —b2 (mod p) číslem 6P_3, dostaneme podle Fermatovy věty
a2r3 = -Ď^1 = -1 (modp).
Protože p = 3 (mod 4), je p — 3 sudé číslo, a proto      G No- Označme
c = ab^~.
Pak c není dělitelné p a platí c2 = a2bp^3 = — 1 (mod p). Umocníme-li poslední kongruenci na       G N, dostaneme
ď-1 = (—l)^ (modp).
Protože p = 3 (mod 4), existuje celé číslo t tak, že p = 3+4ŕ. Pak ovšem ^ = 1 + 2r, což je číslo liché a proto (-l)^-1)/2 = -1. Podle Fermatovy věty naopak platí cp_1 = 1 (mod p), odkud 1 = — 1 (mod p) a p | 2, spor. □
S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řáá čísla moáulo m - jde přitom pouze o jinak nazvaný řád prvku v grupě invertibilních zbytkových tříd modulo m:
Definice. Nechť a £ Z, m £ N (a, m) = 1. Rááem čísla a moáulo m rozumíme nej menší přirozené číslo n splňující
aa = 1   (mod m).
poznámka. To, že je řád definován, plyne z Eulerovy věty - pro každé číslo nesoudělné s modulem je totiž jistě jeho řád nejvýše roven ip(m). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě ip(m) - tato čísla nazýváme primitivními kořeny modulo m a hrají důležitou roli mj. při řešení binomických kongruenci (viz 4.5). Tento pojem je přitom jen jiným názvem pro generátor grupy
(Z£,-)-
29
příklad. Pro libovolné m G N má číslo 1 modulo m řád 1. Číslo — 1 má řád
• 1 pro m = 1 nebo m = 2
• 2 pro m > 2
příklad. Určete řád čísla 2 modulo 7. Řešení.
21 = 2 ^ 1   (mod 7)
22 = 4 ^ 1   (mod 7)
23 = 8 = 1   (mod 7)
Rád čísla 2 modulo 7 je tedy roven 3. □
Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m:
LEMMA. Nechť m E N, a, b E Z, (a, m) = (b, m) = 1. Jestliže a = b (mod m), pak obě čísla a, b maji stejný řád modulo m.
DŮKAZ. Umocněním kongruence a = b (mod m) na n-tou dostaneme an = bn (mod m), tedy an = 1 (mod m) <í=^ bn = 1 (mod m).
□
Lemma. Nechť m E N, a G Z, (a, m) = 1. Je-Zž rad čzsZa a modulo m roven r ■ s, (kde r, s E N), pak řád čísla ď modulo m je roven s.
DŮKAZ. Protože žádné z čísel a, a2, a3,..., ars~ľ není kongruentní s 1 modulo m, není ani žádné z čísel ar, a2r, a3r,..., a^1^' kongruentní s 1. Platí ale {ar)s = 1 (mod m), proto je řád ď modulo m roven s. □
poznámka. Opak obecně neplatí - z toho, že řád čísla ď modulo m je roven s ještě neplyne, že řád čísla a modulo m je r • s. Např pro m = 13 máme:
a = 3, a2 = 9 (mod 13), a3 = 27 = 1 (mod 13) =>• 3 má řád 3 mod 13. b = -4, b2 = 16 ^ 1 (mod 13), 63 = -64 = 1 (mod 13) -4 má řád 3 mod 13.
Přitom (—4)2 = 16 = 3 (mod 13) má stejný řád 3 jako číslo 3, ale číslo —4 nemá řád 2 • 3.
Přesný popis závislosti řádu na exponentu dávají následující 2 věty:
věta 18. Nechť m E n, a E Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná ŕ, s G N U {0} platí
a1 = as   (mod m) <í=^ t = s   (mod r).
30
DŮKAZ. Bez újmy na obecnosti lze předpokládat, že t > s. Vydělíme-li číslo t — s číslem r se zbytkem, dostaneme t — s = q ■ r + z, kde q, z G N0, 0 < z < r.
„<í=" Protože t = s (mod r), máme z = 0, a tedy a*~s = a?r = {ď)q = lq (mod m). Vynásobením obou stran kongruence číslem ď dostaneme tvrzení.
„=^" Z a* = as (mod m) plyne as • a?r+z = ď (mod m). Protože je ď = 1 (mod m), je rovněž a?r+z = az (mod m). Celkem po vydělení obou stran kongruence číslem ď (které je nesoudělné s modulem), dostáváme az = 1 (mod m). Protože z < r, plyne z definice řádu, že z = 0, a tedy r \ t — s. □
Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení (jehož druhá část je přeformulováním Lagrangeovy věty z Algebry pro naši situaci):
DŮSLEDEK. Nechť m G N, a G Z, (a, m) = 1. Označme r řád čísla a modulo m.
(1) Pro libovolné n G N U {0} platí
an = 1   (mod m) <í=^ r | n.
(2) r \ tp{m) DŮKAZ.
(1) stačí v předchozí větě volit t = n, s = r.
(2) zřejmé z (1) díky Eulerově větě volbou n = ip(m).
□
Následující věta je zobecněním předchozího Lemmatu.
VĚTA 19. Nechť m,n G N, a G Z, (a,m) = 1. Je-Zž rad čzsZa a modulo m roven r G N, ?'e rad čísla an modulo m roven -r1-^-
DŮKAZ. Protože       = [r,n], což je zřejmě násobek r, máme
(an)T^) = a[r'n] = 1   (mod m)
(plyne z předchozího Důsledku, neboť r | [r, n]). Na druhou stranu, je-li A; G N libovolné takové, že (an)k = an'k = 1 (mod m), dostáváme (r je řád a), že r | n • k a dále z Věty 5 plyne, že | ■ k a díky nesoudělnosti čísel -r—r a 7^ dostáváme -r—r I A;. Proto ie -r—r řádem
(n,r)      (n,r) (n,r)  * J (n,r)
čísla an modulo m. □
Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu:
LEMMA. Nechť m G N, a, b G Z, (a, m) = (b, m) = 1. Jestliže a je řádu r a b je řádu s modulo m, kde (r, s) = 1, pak číslo a - b je řádu r ■ s modulo m.
31
DŮKAZ. Označme ô řád čísla a ■ b. Pak (ab)s = 1 (mod m) a umocněním obou stran kongruence dostaneme arSbrS = 1 (mod m). Protože je r řádem čísla a, je ar = 1 (mod m), tj. brS = 1 (mod m), a proto s \ rô. Z nesoudělnosti ras plyne s | 5. Analogicky dostaneme i r | 5, a tedy (opět s využitím nesoudělnosti r, s) r ■ s | ô. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto 5 | rs. Celkem tedy ô = r s. □
4. Řešení kongruencí o jedné neznámé
Definice. Nechť m e N, f (x), g (x) E 7h\x\. Zápis
f (x) = g(x)   (mod m) (17)
nazýváme kongruencí o jedné neznáme x a rozumíme jím úkol nalézt množinu řešení, tj. množinu všech takových čísel c G Z, pro která /(c) = g(c) (mod m).
Dvě kongruence o jedné neznámé nazveme ekvivalentní, mají-li stejnou množinu řešení.
Kongruence (17) je ekvivalentní s kongruencí f {x) — g{x) = 0 (mod m).
ez[x]
VĚTA 20. Necht m G N, f (x) G Z[x]. Pro libovolná a,b G Z platí
a = b   (mod m) =^ f {a) = f (b)   (mod m).
DŮKAZ. Nechť je f (x) = cnxn + cn_ixn_1 + • • • + c\x + c0, kde c0, c1;..., cn G Z. Protože a = b (mod m), pro každé i = 1,2,... ,n platí podle Věty 13(2)
Ciď = Cib'1   (mod m),
a tedy sečtením těchto kongruencí pro i = 1,2,...,n a kongruence cq = cq (mod m) dostaneme
cnan+an_ian_1H-----hcia+c0 = cn6n+cn_i6n_1H-----hci&+c0   (mod m),
tj. /(a) = /(&) (mod m). □
důsledek. Množina řešení libovolné kongruence modulo m je sjednocením některých zbytkových tříd modulo m.
Definice. Počtem řešení kongruence o jedné neznámé modulo m rozumíme počet zbytkových tříd modulo m obsahujících řešení této kongruence.
PŘÍKLAD.        (1) Kongruence 2x = 3 (mod 3) má jedno řešení (modulo 3).
(2) Kongruence lOx = 15 (mod 15) má pět řešení (modulo 15).
(3) Kongruence z příkladu (1) a (2) jsou ekvivalentní.
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