Kongruence ooooooooooooo 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 2020 Kongruence ooooooooooooo Obsah přednášky Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Q Kongruence o Základní vlastnosti kongruencí 0 Soustavy lineárních kongruencí o jedné neznámé 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é oooooooooooo Kongruence •oooooooooooo 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 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é oooooooooooo 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. 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é oooooooooooo • 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) 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 m). ^2 = £>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é oooooooooooo • 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 3 = b (mod m) ^ k • a = k • b (mod /c • m). Kongruence ooooo«ooooooo 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í. 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é 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). Soustavy lineárních kongruencí o jedné neznámé oooooooooooo 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) 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é oooooooooooo 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é oooooooooooo Dokončení důkazu. Prvně předpokládejme d = 1. Pak inverze a (mod m) existuje a vynásobením rovnice a • x = b (mod m) touto inverzí dostaneme hledané řešení x = a-1 • 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é oooooooooooo 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); • c^O a soustava, a tedy i původní rovnice, nemá řešení. Kongruence ooooooooooo«o Soustavy lineárních kongruencí o jedné neznámé oooooooooooo Příklad Řešte 39x = 41 (mod 47) 1 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 + lm)b = /cab (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é 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. 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. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé •ooooooooooo 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«oooooooooo Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, at?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/) nemá ř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 = c\ (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é 00*000000000 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í). 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«oooooooo 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«ooooooo Čí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ÄOOOOOO 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. Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod mi) x = C2 (mod rr/2) přepíšeme na ekvivalentní A772 • x = A7?2 • ci (mod mim2) m\ • x = mi • C2 (mod mim2) a vyřešíme podobně jako předtím. 0 něco lepší bývá převedení první rovnice na "parametrický" tvar x = mi • t + ci, dosazení do druhé rovnice mi • t + Ci = C2 (mod rr/2). vyřešení vzhledem k ŕ, dosazení do x = mi • t + c\ a převedení na "implicitní" tvar. Kongruence ooooooooooooo Soustavy lineárních kongruencí o jedné neznámé OOOOOOO0OOOO Příklad ■v Řešte systém kongruencí x = 1 (mod 10) x = 5 (mod 18) x = -4 (mod 25) ■v Řešení Výsledkem je x = 221 (mod 450). Kongruence ooooooooooooo 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". Ř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 kongruencí o jedné neznámé ooooooooo«oo Ř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é oooooooooo«o 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]. 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.