Kongruence ooooooooooooo Soustavy lineárních kongruencř o jedné neznámé ooooooooooo Diskrétní matematika - 2. týden Elementární teorie čísel - kongruence 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 o Základní vlastnosti kongruencí 0 Soustavy lineárních kongruencí o jedné neznámé □ ť5P 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 Soustavy lineárních kongruencř o jedné neznámé 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 9 Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. a 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/-kučera/texty/ATC10.pdf Soustavy lineárních kongruencř o jedné neznámé ooooooooooo Plán přednášky Kongruence ooooooooooooo Q Kongruence • Základní vlastnosti kongruencí □ ť5P 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 taktc^ V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme a ^ b (mod m). a = b (mod m) <□► -ír^J^ < > -E O Q, O Kongruence O0OOOOOOOOOOO Soustavy lineárních kongruencř o jedné neznámé ooooooooooo Lemma Pro libovolná a,b e Z, m 6 N jsou následující podmínky ekvivalentní: O 3 = b (mod m), @ a = b + nit pro vhodné teZ, o m \ a — b. (jsi se © fořsoíeí Kongruence OO0OOOOOOOOOO Základní vlastnosti kongruencí Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Přímo z definice plyne: • a = a (mod m), tj. kongruence podle modulu m je reflexivní, 9 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. 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í, q a = b (mod m) =4> b = a (mod m), tj. kongruence podle modulu m je symetrická, • a = b (mod m), b = c (mod m) =4> a = c (mod m), tj. kongruence podle modulu m je tranzitivní. Jedná se tedy o ekvivalenci, jejíž třídy budeme nazývat zbytkové Dokážeme nyní další vlastnosti: \/S tř/cřy modulo m. iy budeme nazývat zbytkové t • K libovolné straně můžeme přičíst libovolný násobek modulu a = b f (mod m) => a = b -i^k • (mod m). Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • Kongruence podle téhož modulu mužem' vynásobit týmž číslem: ai + ^2 = b\ + t>2 (mod m 3\ = bi (mod rn). 32 = £>2 (mod m) 3 = b (mod rn) 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), . , . . , ) ■ ; ai + 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. ^ \ \ /1 - T "7l. ^. \ . ; . ; => ai • a2 = oi • 02 (mod rn). 32 = 02 (mod m) ---- a = b (mod rn) =4> a = b (mod rn). _ -O c^ £v 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: B\ = b\ (mod m). 32 = £>2 (mod m) a = b (mod m) Kongruence podle téhož mo umocnit na totéž číslo. a\ = bi (mod rn), a2 = £>2 (mod m) a = b (mod rn) a\ + a2 = £>i + £>2 (mod rn) k • a = k • b (mod rn). ďulu můženre násobit, tedy i ai • a2 = £>i • £>2 (mod rn) = bk (mod rn). » Obě strany kongruence můžeme vydělit číslem k, jestliže je nesoudělné s modulem^ k-a = k-b (mod m) a = b (mod m). fTVt) Kongruence OOOO0OOOOOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo • Jestliže n m, pak \í\ \ IW\ \? - a = b (mod m) =4» a = b (mod n). Naopak pokud a = b (mod n), dostáváme m/n = /c možných řešení a = b, a = b + n, ..., nebo a = b + (k — l)n (mod m). ---A ---01 4- vSpv^ >t □ ^ > 4 ^ >■ 4 .= / _ ' 7 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). • Jestliže m = pr?i, m^J je nejmenši společný násobek, pak if i£~ 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 at?i). a = b (mod rr/2) 3 = b (mod m). • Obě strany kongruence a modul lze vynásobit nebo vydělit libovolným číslem ■ i /f \ 3 = 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 příklad z minulého týdne lze ab = 1 (mod m) přeformulovat do tvaru 3 = 1 (mod m), b = 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 ■ 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 5"20 (U^ ^ ^/ >0 0,0 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 G Z platí ap + bp = (a + b)p (mod p) o 1 3 3 1 ľ pra V- A.lp —7 • I I If] \ ___1 *r> ✓------^ J ^ fk^v— 4—__< \ Uäj sou flUA p f-7/ Kongruence Soustavy lineárních kongruencí o jedné neznámé OOOOOO0OOOOOO ooooooooooo Příklad Nalezněte zbytek po dělení čísla 5 číslem 26. Příklad Dokažte, že pro libovolné prvočíslo p a libovolná a, b € 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). !>°i -x ="4 ( i^ít H) y J i _ A 0 o A A —A si 'l Z- -M - Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Inverze modulo m Kongruence OOOOOOO0OOOOO 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ám^inverzík a modulo^n^ Jakožto zbytková třída je toto řešení jediné. □ s Kongruence OOOOOOO0OOOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo nverze 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é. Důkaz. Zobrazení x^(mod m) i—>> a • x (mod m) na zbytkových třídách je Tňrektivnr&vlastnost dělen0: protože je zbytkových tříd na obsou stranách stejně, toiiž m, jedná se o bijekci a jednička 1 (mod m) má jediný vzor. I /* .y = fk^\ ^0 yL^h D X >0 0,0 0 i---> o y ÍJ) h ŕS") Kongruence OOOOOOOO0OOOO Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Nechť m 6 N, a, b e Z. Označme d = (a, rn). Pa/c kongruence a ■ x = b (mod rn) (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 a • x = b (mod m) Nechť m £ N, a, b G Z. Označme d = (a, m). Pak kongruence <\& (\)+~ *}^r(K- (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 OOOOOOOOO0OOO 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í dosta 7 ' nemef hledané e řešení xW1 b (mod m). Kongruence OOOOOOOOO0OOO 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í á4*1 r = tV/b (mod'ľ)- (ŕ ^- (fi ÍřJUL Wí{ 0 0,0 s s\ S) Its 0 40k -s* 0 Kongruence ooooooooooo«o Soustavy lineárních kongruencí o jedné neznámé ooooooooooo Příklad Řešte 39x = 41 (mod 47) Poznámka Teoretický, i když ne příliš praktický postup, pro jednoduchost v případě (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 /.) 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ě {n-l)\ň-l (mod n) i Vcelku přímočarý důRa^ j^ v učebnici. 3 ax fr(lA -H) O^ln-lU C -1, K) ^ &Jt_rvi 4- V ť- ^ Kongruence ooooooooooooo Plán přednášky Soustavy lineárních kongruencí o jedné neznámé ooooooooooo f \ o" y 11 ^ n ť~* & 9 Základní vlastnosti kongruencí 0 Soustavy lineárních kongruencí o jedné neznáme □ s1 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 mj). Kongruence ooooooooooooo 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;). 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 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í 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í. x = Ck (mod trik) Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«ooooooooo Nechť ci, c2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, rr/2) a m = [#77^/772]- Soustava č/\/ol/ kongruencí I 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í Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé o«ooooooooo Nechť ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, rr/2) a m — [mi, rn2]. Soi/srava č/\/ol/ kongruencí J x = ci (mod at?i) l 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 c/), x = C2 (mod d), a tedy i ci = C2 (mod c/). Odtud plyne, že v případě ci ^ C2 (mod c/) soustava nemůže mít řešení. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OO0OOOOOOOO Dokončení důkazu. Uvažujme *>braz^ ^ ^ ^ ^ fc, ^ 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 /r?i, /t?2- Toto zobrazení je injektivní (viz vlastnosti kongruencí). C c '1 Cv-odL in Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OO0OOOOOOOO Uvažujme zobrazeni c (mod m) \-> (c (mod mi), c (mod rn2)) 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í ( vlastnosti kongruencí). Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé ooo«ooooooo 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, 1112] = m a zobrazení je opět bijekce (jen jsme potřebovali zmenšit množinu napravo ze všech dvojic na ty "kompatibilní"). □ Kongruence ooooooooooooo Čí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. 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í modul Soustavy lineárních kongruencí o jedné neznámé oooo«oooooo 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řed psaným i zbytky. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé 000000*0000 Algoritmus Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod at?i) / ' Al-j x = c2 (mod m2) {% ^ přepíšeme na ekvivalentní at?2 • x = at?2 • Ci (mod mim2) at?i • x = at?i • c2 (mod m\m2) a vyřešíme podobně jako předtím. □ ť5P Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé 000000*0000 Algoritmus Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod mi) (=) )( - ^--f- -f. 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. O něco lepší bývá převedení první rovnice na "parametrický" tvar x — mi • t + ci, dosazení do druhé rovnice m1't + c1 = c2 (mod m2), r£&>~ vyřešení vzhledem k t, dosazení do x = mi Q^- c\ a převedení na "implicitní' tvar. < □ ► o ► < t ► < == ► == Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOO0OOO Řešte systém kor/^jencí x = 1 (mod 10) x = 5 (mod 18) x = -4 (mod 25) AH-k<\ s T -S (11) M) >0 Q,o Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooo OOOOOOO0OOO 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 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) -' ^< \ I 4 H \fi~*d ?1 41 -vsltšt g3 ft) 3 Z\ ($1) 5X ^ 2. Z1 tu 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 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é ooooooooooooo ooooooooo«o ■v Řešení 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). 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 V x = 3 (mod 4) x = -3 (mod 81) x = -4 (mod 11), Kongruence Soustavy lineárních kongruencí o jedné neznámé ooooooooooooo ooooooooo«o 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) J, 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. V) o Kongruence ooooooooooooo Modulární reprezentace čísel Soustavy lineárních kongruenci 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 Ji_ Příklad Pětice modulů 3,5,7,11,13 nám pmožní jednoznačně reprezentovat čísla menší než^l5015^a efektivně provádět (v případě potřeby distribuovanej Dež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