Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Diskrétní matematika - 2. týden Elementární teorie čísel - kongruence Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2024 □ ť3? - Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Obsah přednášky Q Kongruence 9 Základní vlastnosti kongruencí • Inverze modulo m 0 Soustavy lineárních kongruencí o jedné neznámé <* Čínská zbytková věta (CRT) • Algoritmus • Modulární reprezentace čísel Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo 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 □ e Kongruence ooooooooooooooo Doporučené zdroje Soustavy lineárních kongruencí o jedné neznámé oooooooooooo 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. William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Kongruence •oooooooooooooo Plán prednášky Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Q Kongruence 9 Základní vlastnosti kongruencí • Inverze modulo m • Čínská zbytková věta (CRT) • Algoritmus • Modulární reprezentace čísel Kongruence 0*0000000000000 Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Kongruence 0*0000000000000 Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Definice Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek, nazývají se a, b kongruentnímodulo m (též kongruentní podle modulu m), což zapisujeme takto: a = b (mod m). V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme a ^ b (mod m). Kongruence oo«oooooooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Lemma Pro libovolná a, b 2 (mod m a\ = b\ (mod m). ^2 = b2 (mod m) a = b (mod m) k • a = k • b (mod m). Kongruence OOOOO0OOOOOOOOO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo 9 Kongruence podle téhož modulu můžeme sčítat, tedy i vynásobit týmž číslem: ai = bi (mod m), . , . . , ; , ; =4> 3i + a2 = b\ + b2 (mod m) 32 = D2 (mod m) a = b (mod m) k • a = k • b (mod m). • Kongruence podle téhož modulu můžeme násobit, tedy i umocnit na totéž číslo. 3l = bl (modm), ^ ai.a2 = bl.b2 (rnodm). a2 = l>2 (mod m) a = b (mod m) ak = bk (mod m). Kongruence OOOOO0OOOOOOOOO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo • Kongruence podle téhož modulu můžeme sčítat, tedy i vynásobit týmž číslem: a\ = b\ (mod m). ^2 = b2 (mod m) a = b (mod m) a\ + a2 = b\ + £>2 (mod m) k • a = k • b (mod m). 9 Kongruence podle téhož modulu můžeme násobit, tedy i umocnit na totéž číslo. a\ = b\ (mod m). 32 = £>2 (mod m) a = b (mod rn) ai • a2 = bi • £>2 (mod rn) = // (mod rn). • Obě strany kongruence můžeme vydělit číslem k, jestliže je nesoudělné s modulem. k-a = k-b (mod rn), (k. m) — 1 =4> a = b (mod m). Kongruence oooooo»oooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo o Jestliže n m, pak a = b (mod m) a = b (mod n). Naopak pokud a = b (mod n), dostáváme m/n = k možných řešení 3 = b. 3 = b + n. ..., nebo a = b + (k — l)n (mod m). Kongruence oooooo»oooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo • Jestliže n | m, pak a = b (mod m) a = b (mod n). Naopak pokud a = b (mod n), dostáváme m/n = k možných řešení a = b. a = b + n. ..., nebo a = b + (k — l)n (mod m). 9 Jestliže m = [mi, m?\ je nejmenší společný násobek, pak a = b (mod m{). a = b (mod rr/2) a = b (mod m) Kongruence oooooo»oooooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo o Jestliže n m, pak a = b (mod m) 3 = b (mod n). Naopak pokud a = b (mod n), dostáváme m/n = k možných řešení 3 = b. 3 = b + n. ..., nebo a = b + (k — l)n (mod m). 9 Jestliže m = [mi, m?\ je nejmenší společný násobek, pak a = b (mod mi), a = b (mod rr/2) 3 = b (mod m) • Obě strany kongruence a modul lze vynásobit nebo vydělit libovolným číslem a = b (mod m) ^ k • a = k • b (mod /c • m). Kongruence OOOOOOO0OOOOOOO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Poznámka Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například příklad z minulého týdne lze přeformulovat do tvaru a = l (mod m), b = 1 (mod m) ab = 1 (mod m). což je speciální případ zpředhozího tvrzení. Kongruence OOOOOOO0OOOOOOO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Poznámka Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například příklad z minulého týdne lze přeformulovat do tvaru a = l (mod m), b = 1 (mod m) což je speciální případ zpředhozího tvrzení. ab = 1 (mod m). Poznámka Nejde o náhodu. Libovolné tvrzení používající kongruence můžeme snadno přepsat pomocí dělitelnosti. Užitečnost kongruencí tedy netkví v tom, že bychom pomocí nich mohli řešit úlohy, které bez nich řešit nejsme schopni, ale v tom, že jde o velmi vhodný způsob zápisu. Osvojíme-li si ho, výrazně tím zjednodušíme jak vyjadřování, tak i některé úvahy. Je to typický jev: v matematice hraje vhodná symbolika velmi závažnou úlohu. Kongruence oooooooo«oooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Příklad Nalezněte zbytek po dělení čísla 520 číslem 26 Kongruence oooooooo«oooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Príklad Nalezněte zbytek po dělení čísla 520 číslem 26 Příklad Dokažte, že pro libovolné prvočíslo p a libovolná a, b E Z platí ap + bp = (a + b)p (mod p) Kongruence oooooooo«oooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Příklad Nalezněte zbytek po dělení čísla 520 číslem 26 Příklad Dokažte, že pro libovolné prvočíslo p a libovolná a, b e Z platí ap + bp = (a + b)p (mod p). Příklad Najděte "inverzi" k číslu 39 modulo 47, tj. najděte x takové, že 39 • x = 1 (mod 47). Kongruence ooooooooo«ooooo Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Inverze modulo m Věta Je-li a nesoudělné s modulem m, tj. (a, m) — 1, pak existuje řešení a • x = 1 (mod m). Toto řešení značíme x = a-1 a nazýváme inverzí k a modulo m. Jakožto zbytková třída je toto řešení jediné. Kongruence ooooooooo«ooooo Inverze modulo m Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Je-li a nesoudělné s modulem m, tj. (a, m) — 1, pak existuje řešení a • x = 1 (mod m). Toto řešení značíme x = a-1 a nazýváme inverzí k a modulo m. Jakožto zbytková třída je toto řešení jediné. Důkaz Zobrazení x (mod m) i—>> a • x (mod m) na zbytkových třídách je injektivní (vlastnost dělení); protože je zbytkových tříd na obsou stranách stejně, totiž m, jedná se o bijekci a jednička 1 (mod m) má jediný vzor. □ Kongruence Soustavy lineárních kongruencí o jedné neznámé oooooooooo»oooo oooooooooooo Nechť m £ N, a, b G Z. Pokud (a, m) = 1, má kongruence a • x = b (mod m) právě jedno řešení x (mod m). V obecném prípade označme d = (a, m). Pa/c má tato kongruence řešení právě tehdy, když d | b; řešením je pak právě d zbytkových tříd x (mod m). Kongruence Soustavy lineárních kongruencí o jedné neznámé oooooooooo»oooo oooooooooooo Nechť m £ N, a, b G Z. Pokud (a, m) = 1, má kongruence a • x = b (mod m) právě jedno řešení x (mod m). V obecném prípade označme d = (a, m). Pa/c má tato kongruence řešení právě tehdy, když d | b; řešením je pak právě d zbytkových tříd x (mod m). Důkaz. Podle předchozí věty inverze a-1 (mod m) existuje a vynásobením rovnice a • x = b (mod m) touto inverzí dostaneme (jediné) řešení b (mod m). □ Kongruence OOOOOOOOOOO0OOO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Dokončení důkazu. V obecném případě d | m | (b — ax); protože také d | a, dostáváme opravdu d | b. Naopak, pokud d | b, vydělíme obě strany i modul největším společným dělitelem d a dostaneme při označení a' — a/d, tí — b/d, m' — m/d ekvivalentní rovnici af • x = tí (mod m) kde již (a;, m') — 1. Podle první části dostaneme jediné řešení x (mod mf), kterému odpovídá právě d řešení x (mod m). □ Kongruence OOOOOOOOOOOO0OO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Algoritmus Začneme s ekvivalentní soustavou dvou kongruencí m • x = O (mod m) a • x = b (mod m) a vždy první rovnici systému nahradíme rovnicí vzniklou odečtením vhodného násobku druhé rovnice (tak abychom koeficient m nahradili jeho zbytkem po dělení číslem a), Kongruence OOOOOOOOOOOO0OO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Algoritmus Začneme s ekvivalentní soustavou dvou kongruencí m • x = O (mod m) a • x = b (mod m) a vždy první rovnici systému nahradíme rovnicí vzniklou odečtením vhodného násobku druhé rovnice (tak abychom koeficient m nahradili jeho zbytkem po dělení číslem a), dokud nedostaneme koeficienty d a 0: d • x = c (mod m) O • x = k (mod m) Kongruence OOOOOOOOOOOO0OO Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Algoritmus Začneme s ekvivalentní soustavou dvou kongruencí m • x = O (mod m) a • x = b (mod m) a vždy první rovnici systému nahradíme rovnicí vzniklou odečtením vhodného násobku druhé rovnice (tak abychom koeficient m nahradili jeho zbytkem po dělení číslem a), dokud nedostaneme koeficienty d a 0: d • x = c (mod m) O • x = k (mod m) Máme dvě možnosti: a k = O a soustava, a tedy i původní rovnice, má řešení vzniklé z první rovnice vydělením d, totiž: x = c/d (mod m/d); k # O a soustava, a tedy i původní rovnice, nemá řešenl 1 ji i □ > Kongruence ooooooooooooo»o Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Příklad Řešte 39x = 41 (mod 47) Kongruence ooooooooooooo»o Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Príklad Řešte 39x = 41 (mod 47) Poznámka Teoretický, i když ne príliš praktický postup, pro jednoduchost v prípade (a, m) = 1: z Bezoutovy věty dostaneme ka + Im = 1, použijeme a • x = b = (/ca + /m)b = kab (mod m) a vydělíme a, takže x = kb (mod m). (Zbytečně počítáme koeficient /.) Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Wilsonova věta Kongruence oooooooooooooo* 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. Kongruence oooooooooooooo* Soustavy lineárních kongruencí o jedné neznámé oooooooooooo 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. Přirozené číslo n > 1 je prvočíslo, právě když (ii-l)! 1 (mod n) Vcelku přímočarý důkaz je v učebnici. □ ť3? - = >0 Q,o Kongruence ooooooooooooooo Plán prednáš Soustavy lineárních kongruencí o jedné neznámé •ooooooooooo r\onP"ľupn C* P • Základní vlastnosti kongruencí • Inverze modulo m 0 Soustavy lineárních kongruencí o jedné neznámé <* Čínská zbytková věta (CRT) • Algoritmus • Modulární reprezentace čísel Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«oooooooooo 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;). Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«oooooooooo 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) Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«oooooooooo 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í. Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé oo»ooooooooo Čí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. Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé oo»ooooooooo Čí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. Věta (Čínská zbytková věta) Necht /7?i,..., m/f e N jsou po dvou nesoudělná, q,...,^ 6Z. Pak platí: soustava x = ci (mod at?i) x = Cf< (mod trik) má jediné řešení modu lo m\ • rr?2 • • • m^. Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOO0OOOOOOOO Důkaz. Budeme se zabývat pouze soustavou dvou kongruencí. Uvažujme zobrazení x (mod mirri2) i—>• (x (mod mi),x (mod m2)), které zbytkové třídě modulo m\m2 přiřadí dvojici odpovídajících zbytkových tříd modulo m\ a modulo tri2. Toto zobrazení je injektivní (viz vlastnosti kongruencí: x = y (mod mi), x = y (mod rr/2) =4> x = y (mod m 1^2))- Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOO0OOOOOOOO Důkaz. Budeme se zabývat pouze soustavou dvou kongruencí. Uvažujme zobrazení x (mod mirri2) i—>• (x (mod mi),x (mod m2)), které zbytkové třídě modulo m\m2 přiřadí dvojici odpovídajících zbytkových tříd modulo m\ a modulo tri2. Toto zobrazení je injektivní (viz vlastnosti kongruencí: x = y (mod mi), x = y (mod rr/2) =4> x = y (mod mirri2)). Na obou stranách přitom máme stejný počet prvků mirri2, jedná se tedy o bijekci a dvojice (ci, C2) má jediný vzor - tím je zbytková třída c (mod mirri2) taková, že c = ci (mod mi), c = C2 (mod m2), tedy řešení soustavy. □ Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOO0OOOOOOO Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, rr/2) am— [mi, rn2]. Soi/sŕa\/a č/\/ol/ kongruencí x = ci (mod at?i) x = C2 (mod at?2) v prípade c\ ^ C2 (mod c/) r?ema řešení. Jestliže naopak c\ = C2 (mod c/), pa/c existuje celé číslo c tak, že x G Z vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod m). Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOO0OOOOOOO Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, rr/2) a m — [mi, rn2]. Soi/srava č/\/ol/ 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 G Z vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod m). Důkaz Má-li soustava nějaké řešení x £ Z, platí nutně x = ci (mod d), x = C2 (mod c/), a tedy i ci = C2 (mod c/). Odtud plyne, že v případě ci ^ C2 (mod d) soustava nemůže mít řešení. Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooo»oooooo Dokončení důkazu. Uvažujme opět zobrazení c (mod m) \-> (c (mod mi), c (mod 1112)) které zbytkové třídě modulo m přiřadí dvojici odpovídajících zbytkových tříd modulo mi, tri2. Toto zobrazení je opět injektivní. Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooo»oooooo Uvažujme opět zobrazení c (mod m) \-> (c (mod mi), c (mod m2)) které zbytkové třídě modulo m přiřadí dvojici odpovídajících zbytkových tříd modulo mi, tri2. Toto zobrazení je opět injektivní. Počítejme dvojice tříd ze zadání, tj. takové, že c\ = C2 (mod d). Libovolné c\ (mod m\) určuje C2 (mod d) a to odpovídá právě 1112/d třídám C2 (mod 1112). Dohromady tak je těchto dvojic at?i • (1112/d) = [mi, at?2] = m a zobrazení je opět bijekce (jen jsme potřebovali zmenšit množinu napravo ze všech dvojic na ty "kompatibilní"). Zbytek důkazu je stejný. □ □ ť3? - = Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooooo oooooo»ooooo Algoritmus Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod at?i) x = C2 (mod RI2) přepíšeme na ekvivalentní rri2 • x = ítí2 • ci (mod m\m2) m\ • x = m\ • C2 (mod m\m2) a vyřešíme podobně jako předtím. □ S Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé oooooo»ooooo Algoritmus Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod at?i) x = C2 (mod m2) přepíšeme na ekvivalentní rr?2 • x = ítí2 • ci (mod rnirr/2) mi • x = mi • C2 (mod minri2) a vyřešíme podobně jako předtím. O něco lepší bývá převedení první rovnice na "parametrický" tvar x — mi • t + ci, dosazení do druhé rovnice /7?i • ŕ + ci = C2 (mod rr/2). vyřešení vzhledem k ŕ, dosazení do x = mi • ŕ + ci a převedení na "implicitní' tvar. n = Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooo«oooo ' Příklad ■v Řešte systém kongruencí X 1 (mod 10) x 5 (mod 18) x -4 (mod 25). Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooo«oooo ' Příklad ■v Ř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) Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOOO0OOO Čínskou zbytkovou větu můžeme použít také „v opačném směru" Příklad Řešte kongruencí 23 941x = 915 (mod 3564) Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOOO0OOO Čínskou zbytkovou větu můžeme použít také „v opačném směru" 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 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. Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooooo ooooooooo»oo Víme, že x e 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). U • ' >-* Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooooo ooooooooo»oo ■v Řešení Víme, že x £ 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), Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooooo 000000000*00 ■v Řešení Víme, že x £ 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. Kongruence ooooooooooooooo Modulární reprezentace čí Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOO0O 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 některých výpočtů s velkými čísly (algebraických, nefunguje např. porovnávání čísel; navíc je potřeba hlídat přetečení). 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. Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé 00000000000» 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] Kongruence ooooooooooooooo Soustavy lineárních kongruencí o jedné neznámé 00000000000» 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.