Literatura Primitivní kořeny Řešení kongruencí a jejich soustav oooooooooooooooooooooooooo ooooooooooooooooooo Diskrétní matematika B - 3. týden Elementární teorie čísel - Primitivní kořeny Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Primitivní kořeny • Malá Fermatova věta, Eulerova věta • Primitivní kořeny Řešení kongruencí a jejich soustav • Lineární kongruence • Lineární kongruence o jedné neznámé • Soustavy lineárních kongruencí o jedné neznámé Primitivní kořeny Řešení kongruencí a jejich soustav oooooooooooooooooooooooooo ooooooooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, průběžně připravovaný e-text. • Předmětové záložky v IS MU 9 Michal Bulant, výukový text k přednášce Elementární teorie čísel, http: //is .muni. cz/el/1431/podzim2012/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. • William Stein, Elementary N um ber Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf a http://wstein.org/edu/2007/spring/ent/ • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Literatura Primitivní kořeny Řešení kongruencí a jejich soustav •ooooooooooooooooooooooooo ooooooooooooooooooo Malá Ferms tova věta Tato tvrzení patří mezi nejduležitější výsledky elementární teorie čísel. Věta (Fermatova, Malá Fermatova) Necht a G Z, p prvočíslo, p\ a. Pak a"-1 = 1 (mod p). Důkaz. Tvrzení vyplyne jako snadný důsledek Eulerovy věty. Dá se ale dokázat i přímo (např. matematickou indukcí nebo kombinatoricky - viz minulá přednáška) □ Důsledek Necht a G Z, p prvočíslo. Pak ap = a (mod p). Literatura Primitivní kořeny o»oooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo l J plná a redukovaná soustava zbytků Definice Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Redukovaná soustava zbytků modulo m je libovolná tp(m)-ť\ce čísel nesoudělných srna po dvou nekongruentních modulo m. Lemma Necht xi, X2,..., x^m) tvoří redukovanou soustavu zbytků modulo m. Je-li a (z Z, (a, m) = 1 pak i čísla a ■ xi,..., a ■ x^mj tvoří redukovanou soustavu zbytků modulo m. Protože (a, m) = 1 a (x,-, m) = 1, platí (a • x,-, m) = 1. Kdyby pro nějaká /',_/' platilo a • xf- = a • x,- (mod m), po vydělení obou stran kongruence číslem a nesoudělným s m dostaneme xf- = x,-(mod m). □ Věta (Eulerova) Necht a G Z, m G N, (a, m) = 1. Pak 3^(m) = 1 (mod m). Důkaz. Bud xi>x2) • • •)xip(m) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a • xi,..., a ■ x^m^ redukovaná soustava zbytků modulo m. Platí tedy, že pro každé / existuje j ( /,_/' G {1,2,..., tp(m)}) tak, že a ■ x; = xj (mod m). Vynásobením dostáváme (a-xi) • (a-x2) • • • (a-x^)) = x1 ■ x2 ■ ■ -x^ (mod m). Po úpravě a^™) • xi • x2 • • • x(p(m) = xi • x2 • • • x(p(m) (mod m) vydělení číslem xi • X2 • • -x^^) dostaneme požadované. □ Literatura Primitivní kořeny ooo»oooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Kryptografická motivace RSA Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, tp(n) = (p — l)(q — 1) [n je veřejné, ale tp(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e,ip(n)) = 1 • např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod (f(n)) 9 zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n) 9 dešifrování šifry C: OT = Dd(C) = Cd (mod n) Literatura Primitivní kořeny oooo»ooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo • Generování klíče. Alice vybere prvočísla p = 2357, q = 2551 a vypočte n = p ■ q = 6012707 a 2 > Literatura Primitivní kořeny ooooooo»oooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo 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) Řád čísla 2 modulo 7 je tedy roven 3. □ Literatura Primitivní kořeny oooooooo»ooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m: Lemma Nechi m 6 N, a, b £ Z, (a, m) = (b, m) = 1. Jestliže a = b (mod m), pak obě čísla a, b mají stejný řád modulo m. Důkaz. Umocněním kongruence a = b (mod m) na n-tou dostaneme a" = bn (mod m), tedy a" = 1 (mod m) -t=^ bn = 1 (mod m). □ Literatura Primitivní kořeny ooooooooo»oooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo 1 Lemma_ Necht m G N, a G Z, (a, m) = 1. Je-li řád čísla a modulo m roven r ■ s, (kde r, s G N), pak řád čísla ar modulo m je roven s. Důkaz. Protože žádné z čísel a, a2, a3,... ,ars 1 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 ar modulo m roven s. □ Literatura Primitivní kořeny oooooooooo»ooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Poznámka Opak obecně neplatí - z toho, že řád čísla ar 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, fa2 = 16 £ 1 (mod 13), fa3 = -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. Literatura Primitivní kořeny OOOOOOOOOOOOOOOOOOOOOOOOOO Řešení kongruencí a jejich soustav OOOOOOOOOOOOOOOOOOO Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Věta Nechi m 6 N, a £ Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná t, s £ N U {0} platí ař = as (mod m) t = s (mod r). Literatura Primitivní kořeny oooooooooooo»ooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo 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 = aqr = (ar)q = lq (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. "=^" Z ař = as (mod m) plyne as • aqr+z = as (mod m). Protože je aľ = 1 (mod m), je rovněž aqr+z = az (mod m). Celkem po vydělení obou stran kongruence číslem as (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. □ Literatura Primitivní kořeny ooooooooooooosoooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo 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 Necht m é n, a é 1 , (a, m) = 1. Označme r řád čísla a modulo m. Q Pro libovolné n G n U {0} platí a" = 1 (mod m) <í=^> r n. O r | (f{m) Literatura Primitivní kořeny oooooooooooooo»ooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Následující věta je zobecněním předchozího Lemmatu. ' Věta Necht m, n G N, a G Z, (a, m) = 1. Je-li řád čísla a modulo m roven r G N, je řád čísla a" modulo m roven t-^t. Důkaz. Protože -fjr^ = [r, n], což je zřejmě násobek r, máme (a")(^T = aM = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r, n]). Na druhou stranu, je-li k G N libovolné takové, že (an)k = ank = 1 (mod m), dostáváme (r ie řád a), že r I n • k a dále víme, že t-^ I 7-^ • k a v J J< \ < (n,r j 1 (n,r j díky nesoudělnosti čísel 7-^ a 7-^ dostáváme I /c. Proto ie řádem čísla a" modulo m. □ Literatura Primitivní kořeny ooooooooooooooo«oooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: ■1 Lemma Nechť m G N, a, b G 2 ', (a, m) = (b, m) = 1. Jestliže a je řádu r a b je řádu s modulo m, kde (r, s) = 1, pa/c č/s/o a • b je řádu r ■ s modulo m. Důkaz. Označme ô řád čísla a • b. Pak {aby = 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. Z/á = 1 (mod m), a proto s | rô. Z nesoudělnosti ras plyne s | ô. Analogicky dostaneme i r | ô, 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 ô | rs. Celkem tedy S = rs._□ Definice Nechť m G N. Celé číslo g G Z, (g, m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (f(m). Lemma Je-li g primitivní kořen modulo m, pak pro každé číslo a G Z, (a, m) = 1 existuje jediné xa £ Z, 0 < xa < v(m) s vlastnostígXa = a (mod m). Funkce a i—>■ xa se nazýva diskrétní logaritmus, př/p. /nc/ex č/s/a 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 < ip(m)}. Důkaz. Předpokládejme, že pro x,y G Z, 0 < x,y < 1. Primitivní kořeny modulo m existují právě tehdy, když m splňuje některou z následujících podmínek: » m = 2 nebo m = 4, • m je mocnina lichého prvočísla » m je dvojnásobek mocniny lichého prvočísla. Dokážeme pouze část tohoto tvrzení, se kterou ve většině případů vystačíme: Tvrzení Nechi p je liché prvočíslo. Pak existují primitivní kořeny modulo p. Diffie-Hellman key exchange Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ -1974) Popis pro laiky - viz http://goo.gl/QBNXP, motivace pro nezasvěcené - viz http://goo.gl/ZOtMP. Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, .. .). » Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné) • Alice vybere náhodné a a pošle ga (mod p) • Bob vybere náhodné b a pošle gb (mod p) • Společným klíčem pro komunikaci je gab (mod p). Literatura Primitivní kořeny ooooooooooooooooooo»oooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Poznámka • Problém diskrétního logaritmu (DLP) • Nezbytná autentizace (man in the middle attack) 9 Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus EIGamal Literatura Primitivní kořeny oooooooooooooooooooo»ooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Existence primitivního kořene. Označme ri, r2,..., rp_i řády čísel 1, 2,..., p — 1 modulo p. Bud' ô = [i, 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 6 = p-l. Nechť ô = q^1 • • • q^k je rozklad ô na prvočísla. Pro libovolné s G {1,... k} existuje c G {1,..., p — 1} tak, že qfs | rc (jinak by existoval menší společný násobek čísel ri, r2,..., rp_i než je ô), tj. ex. b G Z tak, že rc = b ■ qfs. Protože c má řád rc, má číslo gs '■= cb podle tvrzení o řádech mocnin řád roven qfs. Provedením předchozí úvahy pro libovolné s G {1,... k} dostaneme gi,..., a můžeme položit g := gi • • • g>. Z vlastností řádu součinu dostáváme, že řád g je roven součinu řádů čísel gi, ...,gk, tj. číslu q^1 ■■■qckík =6. Literatura Primitivní kořeny ooooooooooooooooooooo»oooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Dokončení. Nyní dokážeme, že S = p — 1. Protože řády čísel 1, 2,..., p — 1 dělí ô, dostáváme pro libovolné x G {1, 2,..., p — 1} vztah xs = 1 (mod p). Kongruence stupně ô modulo prvočíslo p má nejvýše ô řešení (jde vlastně o hledání kořenů polynomů nad tělesem, kterých, jak uvidíme v algebraické části, je nejvýše tolik, kolik je stupeň polynomu). Podle předchozího má však kongruence p — 1 řešení, proto nutně ô > p — 1. Přitom ô | p — 1 (jakožto řád čísla g), proto zejména ô < p — 1, a celkem ô = p — 1. □ Obecně je pro daný modul nalezení primitivního kořene velmi výpočetně náročná operace. Následující věta nám udává ekvivalentní podmínku pro to, aby zkoumané číslo bylo primitivním kořenem, jejíž ověření je o něco snazší než přímý výpočet řádu tohoto čísla. Věta Bud m takové, že modulo m existují primitivní kořeny. Zapišme (p(m) = q^1 ■ ■ ■ q^k. Pak pro libovolné g £ Z, (g, m) = 1 platí, že g je primitivní kořen modulo m, právě když g qi ^ 1 (mod m),... ,g qk ^ 1 (mod m). Literatura Primitivní kořeny ooooooooooooooooooooooo#oo Řešení kongruencí a jejich soustav ooooooooooooooooooo Důkaz. Pokud by platila některá z uvedených kongruencí, znamenalo by to, že řád g je menší než tp(m). Obráceně, pokud g není primitivní kořen, pak existuje d G N, d I ip(m), kde d < ip(m) a gd = 1 (mod m). Je-li u = '£^- > 1, nutně existuje / G {1,..., k} tak, že q-, \ u. Pak ale g q; = g q-, = i (mod m). _□ Literatura Primitivní kořeny oooooooooooooooooooooooo^o Řešení kongruencí a jejich soustav ooooooooooooooooooo Příklad Určíme primitivní kořeny modulo 41. Řešení Protože 1 je prvočíslo, právě když (n-l)! = -l (mod /?) Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo 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, 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 máme (p - 1)! = 1(P-3)/2 • (p - 1) = -1 (mod p). Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav oooooooo»oooooooooo Máme-li soustavu lineárních kongruencí o téže neznámé, můžeme podle předchozí věty 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 x = c,- (mod m,-). Dostaneme tak soustavu kongruencí x = ci (mod mi) x = ci< (mod nik) Zřejmě stačí vyřešit případ k = 2, řešení soustavy více kongruencí snadno obdržíme opakovaným řešením soustav dvou kongruencí. Literatura Primitivní kořeny Řešení kongruencí a jejich soustav oooooooooooooooooooooooooo ooooooooosooooooooo Věta Necht ci, C2 jsou celá čísla, m\, rri2 přirozená. Označme d = (mi, m2). Soustava dvou kongruencí x = ci (mod m\) x = c2 (mod iv2) v případě ci ^ C2 (mod c/) nemá řešení. Jestliže naopak c\ = c2 (mod d), pak existuje celé číslo c tak, že x G Z vyhovuje soustavě, právě když vyhovuje kongruencí' x = c (mod [mi,/7i2]). Důkaz. Má-li soustava nějaké řešení xěZ, platí nutně x = c\ (mod d), x = C2 (mod d), a tedy i ci = C2 (mod d). Odtud plyne, že v případě ci ^ C2 (mod d) soustava nemůže mít řešení. Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav oooooooooo»oooooooo Dokončení důkazu. Předpokládejme dále c\ = c2 (mod d). První kongruenci řešené soustavy vyhovují všechna celá čísla x tvaru x = c\ + tmi, kde ŕ G Z je libovolné. Toto x bude vyhovovat i druhé kongruenci soustavy, právě když bude platit ci + tmi = Q (mod m2), tj. tmi = c2 — ci (mod m2). Podle věty o řešitelnosti lineárních kongruencí má tato kongruence (vzhledem k t) řešení, neboť d = (mi, m2) dělí C2 — ci, a t G Z splňuje tuto kongruenci právě když c2 - Cl mi mod ÍT72 mi \^("^") _|_ rrmn c + r ■ [mi, m2], tj. právě když x = ci + tmi = ci + (c2 - ci) • kde r G Z je libovolné a c = q + (c2 - cx) • (mi/c/)^m2/c'), neboť /D1/D2 = • [mi, m2\. Našli jsme tedy takové c G Z, že libovolné x G Z splňuje soustavu, právě když x = c (mod [mi, m2]), což jsme chtěli dokázat. □ Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooosooooooo Všimněme si, že důkaz této věty je konstruktivní, tj. udává vzorec, jak číslo c najít. Věta nám tedy dává metodu, jak pomocí jediné kongruence zachytit podmínku, že x vyhovuje této soustavě . Podstatné je, že tato nová kongruence je téhož tvaru jako obě původní. Můžeme proto tuto metodu aplikovat i na soustavu -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 kongruencí soustavy sníží o 1, po k — 1 krocích tedy dostaneme kongruenci jedinou, která nám bude popisovat všechna řešení dané soustavy. Ve čtvrtém století se čínský matematik Sun Ze (Sun Tsu) ptal na číslo, které při dělení třemi dává zbytek 2, při dělení pěti zbytek 3 a při dělení sedmi je zbytek opět 2. Řešení Odpověď je (prý) ukryta v následující písni: í£-3^3£ SunziGe Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooo«ooooo Důsledek (Čínská zbytková věta) Nechi mi,,..., £ N jsou po dvou nesoudělná, a\,. Pak platí: soustava . ,ak G Z x = a\ (mod m{) x = 3fr (mod mk) má jediné řešení modulo m\ • m2 • • • m^. Důkaz. Jde o jednoduchý důsledek předchozího tvrzení, který lze ale rovněž elegantně dokázat přímo. □ Označme M := m\m2 • • • mr a n, = M/m-, pro každé /', 1 < i < r. Potom pro libovolné /'je m, nesoudělné s n,, existuje proto nějaké b, G {1,..., m, — 1} tak, že b-,n\ = 1 (mod m,). Všimněme si, že b-,n\ je dělitelné všemi mj, 1 2"2 + • • • + arbrnr. Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooo»ooo Uvědomme si, že jde o docela silné tvrzení (které ve skutečnosti platí v podstatně obecnějších algebraických strukturách), umožňující nám při předepsání libovolných zbytků podle zvolených (po dvou nesoudělných) modulů garantovat, že existuje číslo s těmito předpsanými zbytky. Příklad Řešte systém kongruencí x = 1 (mod 10) x = 5 (mod 18) x = -4 (mod 25). Řešení Výsledkem je x = 221 (mod 450). Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav oooooooooooooooo»oo Čínskou zbytkovou větu můžeme použít také „v opačném směru". Ř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 má tedy 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. Literatura Primitivní kořeny Řešení kongruencí a jejich soustav oooooooooooooooooooooooooo ooooooooooooooooo»o Řešení Víme, že x G Z řešením dané kongruence, právě když je řešením soustavy 23941x = 915 (mod 22) 23941x = 915 (mod 34) 23941x = 915 (mod 11). Vyřešíme-li postupně každou z kongruencí soustavy, dostaneme ekvivalentní soustavu x = 3 (mod 4) x = -3 (mod 81) x = -4 (mod 11), odkud snadno postupem pro řešení soustav kongruencí dostaneme x = —1137 (mod 3564), což je také řešení zadané kongruence. Při počítání s velkými čísly je někdy výhodnější než s dekadickým či binárním zápisem čísel pracovat s tzv. modulární reprezentací (též residue number systém), která umožňuje snadnou paralelizaci výpočtů s velkými čísly. Takový systém je určen /c-ticí modulů (obvykle po dvou nesoudělných) a každé číslo menší než jejich součin je pak jednoznačně reprezentováno /c-ticí zbytků (jejichž hodnoty nepřevyšují příslušné moduly) - viz např. http://goo.gl/oM25m. Literatura Primitivní kořeny oooooooooooooooooooooooooo Řešení kongruencí a jejich soustav ooooooooooooooooooo Příklad Pětice modulů 3, 5, 7,11,13 nám umožní jednoznačně reprezentovat čísla menší než 15015 a efektivně provádět (v případě potřeby distribuovane) běžné aritmetické operace. Vypočtěme např. součin čísel 1234 a 5678, v této modulární soustavě reprezentovaných pěticemi [1,4,2,2,12] a [2,3,1,2,10]. Součin provedeme po složkách a dostaneme [2,2,2,4,3], což na závěr pomocí CRT převedeme zpět na 9662, což je modulo 15015 totéž jako 1234-5678.