Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineárni kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooooooo OOOOOOOOOOO Diskrétní matematika - 3. týden Elementární teorie čísel - Eulerova věta, řád prvku Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooooooo ooooooooooo Obsah přednášky Q Aritmetické funkce • Eulerova funkce cp 0 Malá Fermatova věta, Eulerova věta Q Lineární kongruence Q Soustavy lineárních kongruencí o jedné neznámé Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooooooo ooooooooooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • 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. o William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf o Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé •oooooooooo oooooooooooooo ooooooo ooooooooooo Aritmetické funkce Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených čísel. Definice Rozložme přirozené číslo n na prvočísla: n = p^1 • • • p^k. Hodnotu Mobiovy funkce ji(n) definujeme rovnu 0, pokud pro některé / platí a.i > 1 a rovnu (—1)^ v opačném případě. Dále definujeme Mi) = i- Příklad /z(4) = M22) = 0, M6) = M2 • 3) = (-1)2, M2) = M3) = -1 ] Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé O0OOOOOOOOO oooooooooooooo ooooooo ooooooooooo Dokážeme nyní několik důležitých vlastností Móbiovy funkce, zejména tzv. Móbiovu inverzní formuli. Lemma Pro n eN\{l} platíZdinrid) = 0. Důkaz. Zapíšeme-li n ve tvaru n = p^1 • • • p^\ pak všechny dělitele d čísla n jsou tvaru d = pf1 • • • p^k, kde 0 < /3; < a; pro všechna /£{!,..., k}. Proto din (/3i,-,/3*)e(NU{0})fc 0 1, resp. /(r?) = 1 pro všechna r? G N. Pak pro každou aritmetickou funkci f platí: fol = lof=f a (/o f)(n) = (f o l)(n) = f(d). d\n Dále platí I o ji = jio I = I, neboť c/1 n d\n = /i(c/) = 0 pro všechna n > 1 c/|n podle lemmatu za definicí Móbiovy funkce (pro n = 1 je tvrzení zřejmé). Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOO0OOOOOO oooooooooooooo ooooooo ooooooooooo Věta (Móbiova inverzní formule) Nechť je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(n) = J2d\n 'ze funkci f vyjádřit ve tvaru r(") = EM§)-W d\n Důkaz. Vztah F(n) = J2d\n^(^) 'ze J'ným způsobem zapsat jako F = f o I. Proto F o /i = (f o /) o /i = /ro(/o/i) = f o I = ft což je tvrzení věty. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooo«ooooo oooooooooooooo ooooooo ooooooooooo Definice Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci, která splňuje, že pro všechny dvojice nesoudělných čísel a, b G N platí f (a - b) = f (a) • f {b). Multiplikativními funkcemi jsou např. funkce f (n) = cr(n), f (n) = r(r?), či f (n) = //(r?) nebo, jak brzy dokážeme i tzv. Eulerova funkce f (n) = (p(n). Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO oooooooooooooo ooooooo ooooooooooo Eulerova funkce Definice Nechť n 6 N. Definujme Eulei (!) = 1, (p(5) = 4, (p{6) = 2, je-li p prvočíslo, je zřejmě p-i. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOO0OOO oooooooooooooo ooooooo ooooooooooo Nyní dokážeme několik důležitých tvrzení o funkci cp: Lemma Nechť neN. Pak J2d\n ^(d) = n- Důkaz. Uvažme n zlomků 12 3 n - 1 n 1 1 1 • • • 1 1 ' n n n n n Zkrátíme-li zlomky na základní tvar a seskupíme podle jmenovatelů, snadno dostaneme právě uvedené tvrzení. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOO0OO oooooooooooooo ooooooo ooooooooooo Důkaz S využitím předchozího lemmatu a Móbiovy inverzní formule dostáváme >l = n " ^-----7" + """ + din n Pi • • • Pk = n • 1 - 1 - Pi Pk Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOO0O oooooooooooooo ooooooo ooooooooooo Předchozí výsledek lze obdržet i bez použití Móbiovy inverzní formule pomocí principu inkluze a exkluze na základě zjištění počtu čísel soudělných snv určitém intervalu. Důsledek Necht a, b e N, (a, b) = l. Pak ip{a ■ b) = ip(a) ■ ip{b) Poznámka Rovněž toto tvrzení lze odvodit nezávisle na základě poznatku (r?, atí) = 1 (r?, a) = 1 A (r?, b) = 1. Spolu se snadno odvoditelným výsledkem ^(p«) = pa - pa~ľ = (p - 1) • p .a—l pak lze odvodit vztah pro výpočet cp již třetím způsobem. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé oooooooooo* oooooooooooooo ooooooo ooooooooooo Příklad Vypočtěte (f{72) Řešení 72 = 23 • 32 ip(72) = 72 • (1 - \) ■ (1 - §) = 24, alternativně y>(72) = y>(8) • y>(9) = 4 • 6 = 24. □ Příklad Dokažte, že Vn G N : ^(4n + 2) = ^(2n + 1) 1 Řešení Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO «0000000000000 ooooooo ooooooooooo Malá Fermatova věta Tato tvrzení patří mezi nejdůležitější výsledky elementární teorie v ' I cisel. Věta (Fermatova, Malá Fermatova) Nechť a G Z, p prvočíslo, p\ a. Pak ap~x = 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) □ Důsledek Necht a £ Z, p prvočíslo. Pak ap = a (mod p) Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo o«oooooooooooo ooooooo ooooooooooo Upíná 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á (p(m)-ť\ce čísel nesoudělných s m a po dvou nekongruentních modulo m. Lemma Necht xi, X2,..., tvoří redukovanou soustavu zbytků modulo m. Je-li a £ Z, (a, m) = 1 pak i čísla a • xi,..., a • x^(m) r\/on redukovanou soustavu zbytků modulo m. Důkaz. Protože (a, m) = 1 a (x,-, m) = 1, platí (a • x,-, m) = 1. Kdyby pro nějaká i J platilo a • x; = a • xy (mod m), po vydělení obou stran kongruence číslem a nesoudělným s m dostaneme x; = xy (mod m). □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OO0OOOOOOOOOOO ooooooo ooooooooooo Eulerova věta r Věta (Eulerova) _ Necht a G Z, m G N, (a, m) = 1. Pak a 2 Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo ooooo«oooooooo ooooooo ooooooooooo Příklad Určete řád čísla 2 modulo 7. ■v Ř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. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooo«ooooooo ooooooo ooooooooooo Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m\ Lemma Necht m 6 N, a, b e Z, (a, m) — {b. m) — 1. Jestliže a = b (mod m), pak obě čísla a, b mají stejný rád modulo m. Důkaz. Umocnením kongruence a = b (mod m) na r?-tou dostaneme an = bn (mod m), tedy an = 1 (mod m) <^=^> bn = 1 (mod m). □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo ooooooo«oooooo ooooooo ooooooooooo Lemma Necht m G N, a £ Z, (a, m) = 1. Je-li řád čísla a modulo m roven r • s, (kde r, s e N), pak rád čísla ar modulo m je roven s. Důkaz. ] Protože žádné z w . 2 3 ci sei a i a ^ a ,... , ars 1 není kongruentní s 1 modulo m, není ani žádné z čísel ~r J2r ~3r ~(s—l)r d . d . d j . . . y d kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ar modulo m roven s. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOO0OOOOO ooooooo ooooooooooo 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á rád 3 mod 13. b = -4, b2 = 16 ^ 1 (mod 13), b3 = -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. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOO0OOOO ooooooo ooooooooooo Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Věta Necht m G N, a £ Z, (a, m) — 1. Označme r rád čísla a modulo m. Pak pro libovolná t, s e N U {0} platí ař = as (mod m) t = s (mod r). Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOO0OOO ooooooo ooooooooooo 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 No, 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 rn). Protože je ar = 1 (mod m), je rovněž aqr+z = az (mod rn). 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 ŕ — s. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOO0OO ooooooo ooooooooooo Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení Důsledek Nechť m e N, a e Z », (a, m) — 1. Označme r rád čísla a modulo m. O Pro libovolné n GNU {0} platí an = 1 (mod m) r n. O r | (p(m) Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooo«o ooooooo ooooooooooo Následující věta je zobecněním předchozího Lemmatu Necht m, n 6 N, a e Z, (a, m) = 1. Je-// řac/ č/s/a a modulo m roven r 6 N, /e řác/ č/s/a an modulo m roven -r^- Důkaz Protože jy^j = [r, r?], což je zřejmě násobek r, máme (a")(^) = a^ = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r, /?]). Na druhou stranu, je-li /c 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 víme, že -r-^ I • k a V j 7' ' (n,r) I (n,r) díky nesoudělnosti čísel a dostáváme k. Proto je y {n,r) (n,r) (n,r) J řádem čísla an modulo m. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO 0000000000000« ooooooo ooooooooooo Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma_J Necht m £ N, a, b £ Z b je řádu s modulo m, modulo m. , (a, m) = kde (r, s) (b, m) = 1. Jestliže a je řádu r a = 1, pak číslo a • b je řádu r • s Důkaz. i Označme S řá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 | rS. Z nesoudělnosti ras plyne s | S. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r • s | S. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto S | rs. Celkem tedy ô = rs. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo •oooooo ooooooooooo Kongruence o jedné neznámé Definice Nechť m G N, f(x),g(x) G Z [x]. Zápis f [x) = g(x) (mod m) nazýváme kongruencí o jedné neznámé 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á f (c) = g(c) (mod m). Dvě kongruence o jedné neznámé nazveme ekvivalentní, mají-li stejnou množinu řešení. Uvedená kongruence je ekvivalentní s kongruencí f (x) — g (x) = 0 (mod m). v-v-' G Z [x] Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO O0OOOOO ooooooooooo Hledání řešení výčtem všech možností Věta Necht m e 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. Necht je f (x) = cnxn + cn _ixn_1 H-----h cix + c0, kde co, ci,..., cn e Z. Protože a = b (mod m), pro každé / = 1, 2,..., r? platí c,-a' = c;b' (mod m), a tedy sečtením těchto kongruencí pro / = 1, 2,... , n a kongruence co = co (mod m) dostaneme cnan H-----h cia + c0 : = cnbn + • • • + cib + co (mod m), tj. ŕ(a) = f (b) (mod m). □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OO0OOOO ooooooooooo Počet řešení kongruence 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 O Kongruence 2x = 3 (mod 3) má jedno řešení (modulo 3). Q Kongruence lOx = 15 (mod 15) má pět řešení (modulo 15). O Kongruence z příkladu (1) a (2) jsou ekvivalentní. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooo«ooo ooooooooooo Necht m £ N, a, b £ Z. Označme d = (a, m). Pak kongruence ax = b (mod m) (o jedné neznámé x) má řešení právě tehdy, když d | b. Pokud platí d | b, má tato kongruence právě d řešení (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\d\a-c — ba Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo oooo«oo ooooooooooo Dokončení důkazu. Obráceně dokážeme, že pokud d | b, pak má daná kongruence právě d řešení modulo m. Označme ai, b\ £ Z a m\ £ N tak, že a = d - ai, b — d - b\ a m = d • m\. Řešená kongruence je tedy ekvivalentní s kongruencí a\ • x = b\ (mod mi), kde (ai, m\) — 1. Tuto kongruencí můžeme vynásobit číslem <9^(mi) 1 a díky Eulerově větě obdržíme x = b\ • a^mi^ 1 (mod mi). Tato kongruence má jediné řešení modulo mi a tedy d = řešení modulo m. m/mi □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooooo«o ooooooooooo Následující příklad ukáže, že postup uvedený v důkazu věty obvykle není tím nejefektivně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) O Nejprve využijeme Eulerovu větu, stejně jako v důkazu předchozí věty. O Další možností je využít Bezoutovu větu. O 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 4x = 3 x = -11 (mod 47) -8x = -6 (mod 47) (mod 47) 4x = -44 (mod 47) (mod 47) x = 36 (mod 47) Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO oooooooooooooo oooooo* ooooooooooo Wilsonova věta 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 (Wilsonova) Přirozené číslo n > 1 je prvočíslo, právě když (n-l)\ = -1 (mod n) Vcelku přímočarý důkaz je v učebnici. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OOOOOOO «0000000000 Soustavy lineárních kongruencí 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 = q (mod m;). Dostaneme tak soustavu kongruencí x = ci (mod at?i) x = Ck (mod trik) 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í. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OOOOOOO O0OOOOOOOOO Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, m2). Soustava dvou kongruencí x = ci (mod at?i) x = C2 (mod at?2) v případě ci ^ C2 (mod c/) r?ema řešení Jestliže naopak c\ = C2 (mod c/), pa/c existuje celé číslo c tak, že x £ Z vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod [at?i. at?2])- Důkaz. Má-li soustava nějaké řešení x £ Z, platí nutně x = c± (mod cf), x = C2 (mod d), a tedy i ci = C2 (mod cf). Odtud plyne, že v případě ci ^ C2 (mod c/) soustava nemůže mít řešení. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OOOOOOO OO0OOOOOOOO 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 c\ + tmi = c2 (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 = (/7?i, m2) dělí c2 — ci, a t G Z splňuje tuto kongruenci právě když c2 - ci /mi\^(^r)-i / m2 —ď~ • (t) (mod t tj. právě když x = ci + rmi = ci + (c2-ci).(^)^(^) + r^ = c + r>i,m2], kde r G Z je libovolné a c = q + (c2 - ci) • {mi/d)^m2/d\ neboť mim2 = c/ • [mi, rn2]. 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. □ t = Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooooooo ooo«ooooooo 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. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO oooooooooooooo ooooooo ooooooooooo Čínská zbytková věta (CRT) 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. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO oooooooooooooo ooooooo ooooooooooo Necht /7?i,,..., m/f e N jsou po dvou nesoudělná, ai,...,a^6Z. Pak platí: soustava x = a\ (mod m\) x = a^ (mod m^) má jediné řešení modulo m\ • rr?2 • • • m^. Důkaz. Jde o jednoduchý důsledek předchozího tvrzení, který lze ale rovněž elegantně dokázat přímo. □ Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OOOOOOO 000000*0000 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. Řešte systém kongruencí x x x 5 1 (mod 10) (mod 18) (mod 25). ■v Řešení Výsledkem je x = 221 (mod 450). Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo oooooooooooooo ooooooo ooooooooooo Čí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 v?(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. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OOOOOOO OOOOOOOO0OO Řešení Víme, že x 6 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. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO oooooooooooooo ooooooo ooooooooooo Modulární reprezentace čísel 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. Aritmetické funkce Malá Fermatova věta, Eulerova věta Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO OOOOOOOOOOOOOO OOOOOOO 0000000000« 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.