Diskrétní matematika - 2. týden Elementární teorie čísel - kongruence námé Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Kongruence ooooooooooooo Obsah přednášky Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Q Kongruence * Základní vlastnosti kongruencí Q Soustavy lineárních kongruencí o jedné neznámé 4 □ ► 4 [fP Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Doporučené zdroje Kongruence ooooooooooooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne □ ť5P Kongruence ooooooooooooo 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 Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Kongruence ooooooooooooo Plán prednášky Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Kongruence o Základní vlastnosti kongruencí Kongruence •oooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 •oooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 r, kde 0 < r < m, 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 O0OOOOOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo r Lemma i Pro libovolná a, b b = a (mod m), tj. kongruence podle modulu m je symetrická, • a = b (mod m), b = c (mod m) a = c (mod m), tj. kongruence podle modulu m je tranzitivní. Jedná se tedy o ekvivalenci, jejíž třídy budeme nazývat zbytkové třídy modulo m. Kongruence OO0OOOOOOOOOO Základní vlastnosti kongruencř Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Přímo z definice plyne: 9 a = a (mod m), tj. kongruence podle modulu m je reflexivní, v a = b (mod m) =4> b = a (mod m), tj. kongruence podle modulu m je symetrická, • a = b (mod m), b = c (mod m) a = c (mod m), tj. kongruence podle modulu m je tranzitivní. Jedná se tedy o ekvivalenci, jejíž třídy budeme nazývat zbytkové třídy modulo m. Dokážeme nyní další vlastnosti: • K libovolné straně můžeme přičíst libovolný násobek modulu: a = b (mod m) a = b + k • m (mod m). Kongruence OOO0OOOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • Kongruence podle téhož modulu můžeme sčítat, tedy i vynásobit týmž číslem: a± + a2 = b\ + £>2 (mod m) a\ = b\ (mod m). 32 = £>2 (mod m) a = b (mod m) k • a = k • b (mod m). Kongruence OOO0OOOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • Kongruence podle téhož modulu můžeme sčítat, tedy i vynásobit týmž číslem: ai = bi (mod m), . , . . , ) ■ ; 3i + a2 = bi + 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. a\ • a2 = b\ • £>2 (mod m) ai = b\ (mod rn), a2 = £>2 (mod rn) a = b (mod rn) =4> a^ = bk (mod rn). Kongruence OOO0OOOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • Kongruence podle téhož modulu můžeme sčítat, tedy i vynásobit týmž číslem: a\ = b\ (mod m). 32 = £>2 (mod m) a = b (mod m) a\ + a2 = b\ + £>2 (mod m) k • a = k • b (mod m). Kongruence podle téhož modulu můžeme násobit, tedy i umocnit na totéž číslo. a\ = b\ (mod rn). 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 OOOO0OOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • 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). Kongruence OOOO0OOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • 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). 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) Kongruence OOOO0OOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • 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 ooooo«ooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Poznámka Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například príklad z minulého týdne lze přeformulovat do tvaru 3 = 1 (mod m), b = 1 (mod m) ab = 1 (mod m) což je speciální případ zpředhozího tvrzení. Kongruence ooooo«ooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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í. 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 OOOOOO0OOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Příklad Nalezněte zbytek po dělení čísla 520 číslem 26 Kongruence OOOOOO0OOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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) Kongruence OOOOOO0OOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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). <□► < rS1 ► <■€.*■ < ► -E O Q, O Kongruence OOOOOOO0OOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Inverze modulo m 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é. Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Inverze modulo m Kongruence OOOOOOO0OOOOO 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 OOOOOOOO0OOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Nechť m 6 N, a, b e Z. Označme d = (a, m). Pa/c kongruence a • x = 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). Kongruence OOOOOOOO0OOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Nechť m 6 N, a, b e Z. Označme d = (a, m). Pa/c kongruence a • x = 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á d | (a • x, m) — (b, m) \ b. Kongruence ooooooooo«ooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Dokončení důkazu. Prvně předpokládejme d = 1. Pak inverze a 1 (mod m) existuje a vynásobením rovnice a • x = b (mod m) touto inverzí dostaneme hledané řešení b (mod m). Kongruence ooooooooo«ooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Dokončení důkazu. Prvně předpokládejme d = 1. Pak inverze a 1 (mod m) existuje a vynásobením rovnice a • x = b (mod m) touto inverzí dostaneme hledané řešení b (mod m). Obecně prvně obě strany i modul vydělíme největším společným dělitelem d, dostaneme při označení a1 — a/d, tí — b/d, mr — m/d ekvivalentní rovnici af • x = tí (mod m) kde již (a;, m') — 1 a postupujeme podle první části. □ Kongruence OOOOOOOOOO0OO Algoritmus Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 rovnici vzniklou odečtením vhodného násobku druhé rovnice (tak abychom koeficient m nahradili jeho zbytkem po dělení číslem a), Kongruence OOOOOOOOOO0OO Algoritmus Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 rovnici 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 = b' (mod m) O • x = c (mod m) Kongruence OOOOOOOOOO0OO Algoritmus Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 rovnici 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 = b' (mod m) O • x = c (mod m) Máme dvě možnosti: o c = O a soustava, a tedy i původní rovnice, má řešení vzniklé z první rovnice vydělením d, totiž: x = tí j d (mod m/d); o c # O a soustava, a tedy i původní rovnice, nemá řešenu 1 i □ ► Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo«o ooooooooooo Príklad Řešte 39x = 41 (mod 47) Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooo«o ooooooooooo 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 = (ka + lm)b = kab (mod m) a vydělíme a, takže x = kb (mod m). (Zbytečně počítáme koeficient /.) □ s Kongruence 000000000000« Wilsonova věta Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 000000000000« Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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. Kongruence ooooooooooooo Plán prednášky Soustavy lineárních kongruencí o jedné neznámé ooooooooooo f \ o" Kii ^ n ť~*& 9 Základní vlastnosti kongruencí 0 Soustavy lineárních kongruencí o jedné neznámé □ ť5P Kongruence ooooooooooooo Soustavy lineárních kongruencí Soustavy lineárních kongruencí o jedné neznámé •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 = q (mod m;). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé •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 ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé •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 ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«ooooooooo 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 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). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«ooooooooo Necht ci, C2 jsou celá čísla, mi. m2 přirozená. Označme d = (mi, at?2) am— [mi, rn2]. Soi/sŕa\/a č/\/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 c\ = C2 (mod c/). Odtud plyne, že v případě ci ^ C2 (mod d) soustava nemůže mít řešení. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOOOOOO Dokončení důkazu. Uvažujme 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 injektivní (viz vlastnosti kongruencí). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OO0OOOOOOOO ■ Uvažujme 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 injektivní (viz vlastnosti kongruencí). Předpokládejme prvně (mi, RI2) = 1, pak m — m\m2 a na obou stranách máme stejný počet prvků, jedná se tedy o bijekci a dvojice (ci, C2) má jediný vzor - tím je zbytková třída c (mod m) taková, že c = ci (mod mi), c = C2 (mod 1112), tedy řešení soustavy. □ Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooo«ooooooo Dokončení důkazu. Uvažujme 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 injektivní (viz vlastnosti kongruencí). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooo«ooooooo Dokončení důkazu. Uvažujme 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 injektivní (viz vlastnosti kongruencí). Nechť nyní d je libovolné. Počítejme dvojice tříd ze zadání, tj. takových, ž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 m\ • (rri2/d) = [mi, rr/2] = m a zobrazení je opět bijekce (jen jsme potřebovali zmenšit množinu napravo ze všech dvojic na ty "kompatibilní"). □ Soustavy lineárních kongruencí o jedné neznámé oooo«oooooo Čínská zbytková věta (CRT) Kongruence ooooooooooooo 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. Důsledek (Čínská zbytková věta) 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^. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOÄOOOOO 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. Kongruence ooooooooooooo Algoritmus Soustavy lineárních kongruencí o jedné neznámé 000000*0000 Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod at?i) x = C2 (mod RI2) přepíšeme na ekvivalentní rr?2 • x = ítí2 • ci (mod m\m2) mi • x = mi • C2 (mod minri2) a vyřešíme podobně jako předtím. □ ť5P Kongruence ooooooooooooo Algoritmus Soustavy lineárních kongruencí o jedné neznámé 000000*0000 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 rnirr/2) mi • x = mi • C2 (mod mirri2) a vyřešíme podobně jako předtím. O něco lepší bývá převedení první rovnice na "parametrický" tvar x = /7?i • 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 ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOO0OOO Příklad ■v Řešte systém kongruencí X 1 (mod 10) X 5 (mod 18) X -4 (mod 25). Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooo OOOOOOO0OOO Príklad ■v Reste systém kongruencí x 1 (mod 10) x 5 (mod 18) x -4 (mod 25). Rešení Výsledkem je x = 221 (mod 450). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOOO0OO Čí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) 1 Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOOO0OO Čí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. Kongruence ooooooooooooo Soustavy lineárních kongruenci o jedné neznámé OOOOOOOOO0O Ř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). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooo«o Rešení 1 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 ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooo«o Ř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 ooooooooooooo Modulární reprezentace čísel Soustavy lineárních kongruencí o jedné neznámé 0000000000« 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. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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 ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooooooooooo 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.