MB141 - 11. přednáška Kongruence Martin Čadek s využitím přednášek pro předmět MB104 Jarní semestr 2020 11. přednáška Kongruence Osnova 11. přednášky • Kongruence a počítání s nimi • Malá Fermatova věta • Eulerova funkce a Eulerova věta • Řešení lineárních rovnic s kongruencemi • Čínská zbytková věta a řešení soustav lineárních kongruencí 11. přednáška Kongruence 2/29 Pojem kongruence 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). 11. přednáška Kongruence 3/29 Kongruence jako ekvivalence Lemma Pro libovolná a,beZ,meN jsou následující podmínky ekvivalentní: O a = b (mod m), Q a = b + mt pro vhodné t e Z, O m\ a - b. Přímo z definice plyne, že kongruence podle modulu m je reflexivní (tj. a = a (mod m) platí pro každé a e Z), symetrická (tj. pro každé a, b eZz a = b (mod m) plyne b = a (mod m)) a tranzitivní (tj. pro každé a, b, c eZz a = b (mod m) a b = c (mod m) plyne a = c (mod m)) relace, jde tedy o ekvivalenci. 11. přednáška Kongruence 4/29 Základní vlastnosti kongruencí I Ukážeme nyní další vlastnosti kongruencí, které jsou důležité při počítání: • Kongruence podle téhož modulu můžeme sčítat. Libovolný sčítanec můžeme přenést s opačným znaménkem z jedné strany kongruence na druhou. K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu. Je-li a-i = fr| (mod m) a a2 = b2 (mod m), existují podle lemmatu U, h e Z tak, že a-i = fr| + mU, a2 = b2 + mt2. Pak ovšem a-i + a2 = £>i + b2 + m(ři + t2) a opět podle lemmatu a-i + a2 = fr| + Ď2 (mod m). Sečteme-li kongruenci a + Ď = c (mod m) s kongruencí -b = b (mod m), která zřejmě platí, dostaneme a = c - b (mod m). Sečteme-li kongruenci a = b (mod m) s kongruencí mk = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mk = b (mod m). 11. přednáška Kongruence 5/29 Základní vlastnosti kongruencí II • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. • Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. • Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. Důkazy těchto tvrzení se provádějí stejným způsobem jako důkaz z předchozí strany. 11. přednáška Kongruence 6/29 Základní vlastnosti kongruencí III • Jestliže kongruence a = b platí podle modulů m1,..., mk, platí i podle modulu, kterým je nejmenší společný násobek [m-i,..., mk] těchto čísel. Jestliže a = b (mod m1), a = ď (mod m2),..., a = b (mod mk), podle lemmatu je rozdíl a - b společný násobek čísel A77-|, A772,..., mk a tedy je dělitelný jejich nejmenším společným násobkem [m-i, m2,..., a^], odkud plyne a = ď (mod [/77-i ?... 5 /T?/c])- • Jestliže kongruence platí podle modulu m, platí podle libovolného modulu d, který je dělitelem čísla m. • Jestliže je jedna strana kongruence a modul dělitelný nějakým celým číslem, musí být tímto číslem dělitelná i druhá strana. 11. přednáška Kongruence 7/29 Poznámka a příklad 1 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. Příklad (1) Nalezněte zbytek po dělení čísla 5^u číslem 26. Protože 52 = 25 = -1 (mod 26), platí 520 = (52)10 = (-1)10 = 1 (mod 26), a tedy zbytek po dělení čísla 520 číslem 26 je jedna. 11. přednáška Kongruence 8/29 Příklady 2 a 3 Příklad (2) Dokažte, že pro libovolné n g N je 37n+2 + 16n+1 + 23n dělitelné sedmi. Platí 37 = 16 = 23 = 2 (mod 7), a tedy podle základních vlastností kongruencí platí 37"+2+16"+1 +23" = 2n+2+2"+1 +2" = 2n(4+2+1) = 0 (mod 7) Příklad (3) Dokažte, že číslo n = (8355 + 6)18 - 1 je dělitelné číslem 112. J Rozložíme 112 = 7-16. Protože (7,16) = 1, stačí ukázat, že 7 | n a 16 | n. Platí 835 = 2 (mod 7), a tedy n = (25 + 6)18 - 1 = 3818 - 1 = 318 - 1 = = 276 - 1 = (-1)6 - 1 = 0 (mod 7), 11. přednáška Kongruence 9/29 Příklad 3 proto 7 | n. Podobně 835 = 3 (mod 16), a tedy n = (35 + 6)18 - 1 = (3 • 81 + 6)18 - 1 = (3 ■ 1 + 6)18 - 1 = = 918 - 1 = 819 - 1 = 19 - 1 = 0 (mod 16), proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat. Příklad Najdete "inverzi" k číslu 39 modulo 47, tj. najdete x takové, že 39 x = 1 (mod 47). Počítáme (mod 47): 39 = -8, proto -8x = 1. Vynásobíme 6 a odečteme 47x = 0, dostaneme x = -6 = 41. 11. přednáška Kongruence 10/29 Příklad (4) Najděte "inverzi" k číslu 39 modulo 235, tj. najděte x takové, že 39 x= 1 (mod 235). Protože 235 = 5 • 47 a čísla 5 a 47 jsou nesoudělná, je kongruence 39x = 1 (mod 235) ekvivalentní se dvěma kongruencemi 39x = 1 (mod 47) a 39x = 1 (mod 5) Podle předchozí úlohy má prvá řešení x = 41 (mod 47). Řešení druhé je x = 4 (mod 5). Tedy podle prvé kongrunce je x = 47y + 41, dosazením do druhé dostaneme 47y + 41=4 (mod 5), ekvivalentně 2y + 1 =4 (mod 5), 2y = 3 (mod 5), 2y == 2 (mod 5), tedy y = -1 =4 (mod 5). Tedy y = 5z + 4. Zpětným dosazením do x dostaneme x = 47(5z + 4) + 41 = 235z + 229 = 229. Malá Fermatova věta Tato tvrzení patří mezi nejdůležitější výsledky elementární teorie čísel. Věta (Malá Fermatova věta) Nechť p je prvočíslo a nechť aeZje takové, že p\ a. Pak ap~A = 1 (mod p). Prvně dokážeme indukcí, že ap = a (mod p) pro všechna a přirozená. Pro a = 1 to platí. Předpokládejme, že ap = a pro nějaké a > 1. Potom pomocí binomické věty (a + 1 )P = Yľk=o {k)ak = aP + 1' neboť pro všechna k = 1,2,...,p- 1 platí, žep| (£) = díky tomu, že p je prvočíslo. Dále použijeme indukční předpoklad (a + 1 )p = ap + 1 = a + 1. Platí-li, že ap = a (mod p), pak číslem a, které není násobkem p, můžeme dělit a dostaneme a^"1 = 1 (mod p). 11. přednáška Kongruence 12/29 Příklad 5 Všimněte si, že jsme při důkazu dokázali ap = a (mod p) pro všechna a. Příklad (5) Zjistěte zbytek po dělení čísla 2 1 480 číslem 47. 47 je prvočíslo. 47-1 = 46 a 480 = 10 • 46 + 20. Proto podle Fermatovy věty dostáváme 2 1 480 = (2 1 46)10 - 2 1 20 = 110 - 2 1 20 = (2 1 2)10 = 44110 = 1810 = (182)5 = (-5)5 = 625 • (-5) = 14 • (-5) = 24 (mod 47). 11. přednáška Kongruence 13/29 Eulerova funkce Malou Fermatovu větu lze zobecnit. K tomu budeme potřebovat Eulerovu funkci. Je-li p prvočíslo, pak počet celých čísel v intervalu [1, p], která jsou nesoudělná s p je p - 1. To je exponent vyskytující se ve Fermatově větě. Definice Nechť n e N. Eulerovu funk< čísel v intervalu [1, n] nesou (1) = 1, (p{5) = 4, ) = 1. Pak ) = 2 11. přednáška Kongruence 17/29 Příklad 7 Příklad (7) Určete rád čísla 2 modulo 7. ■ Řešení: 21 = 2 £ 1 (mod 7) 22 = 4 ^ 1 (mod 7) 23 = 8 = 1 (mod 7) Rád čísla 2 modulo 7 je tedy roven 3. 11. přednáška Kongruence 18/29 Lineární kongruence o jedné neznámé Nechť m e N, a, b e Z. Označme d = (a, m). Pa/c kongruence ax = b (mod at?) (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). Řešením modulo m myslíme zbytkovou třídu. Např. zbytková třída 3 (mod 7) je množina {7k + 3gZ; k eZ}. Příklad O Kongruence 2x = 1 (mod 3) má jedno řešení (modulo 3). O Kongruence 10x = 5 (mod 15) má pět řešení (modulo 15). 11. přednáška Kongruence 19/29 Důkaz Kongruence 2x = 1 (mod 3) má řešení x = 2 (mod 3). Kongruence 10x = 5 (mod 15) má řešení 2,3 + 2 = 5, 6 + 2 = 8,9 + 2 = 11,12 + 2 = 14 (mod 15). Důkaz předchozí věty provedeme pomocí Eulerovy věty: 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 d = (a, m), pak d dělí také a • c - b. A protože dělí a, musí dělit také b. Obráceně dokážeme: pokud d | b, pak má daná kongruence právě d řešení modulo m. Označme a\,b^ e Z a m1 g N tak, že a = d • a-i, b = d • fr| a m = d • m^. Řešená kongruence je tedy ekvivalentní s kongruencí a-i • x = ď-i (mod m-i), kde (a-i, m1) = 1. 11. přednáška Kongruence 20/29 Dokončení důkazu Tuto kongruenci můžeme vynásobit číslem ä\ Eulerově větě obdržíme V?(A7?1)-1 a díky — o^(™l) xx — 0^(^l)-1 x = a i x = a i • Ď-i (mod A77-|). Tato kongruence má jediné řešení modulo m1 a tedy d = m/m-i řešení modulo m. Ta jsou a^(A77l)_1 • + km^, kde /c = 0,1,2,...,cř-1. 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. 11. přednáška Kongruence 21/29 Příklad 8 Řešte 39x = 41 (mod 47) (1) Nejprve využijeme Eulerovu větu, stejně jako v důkazu. (2) Další možností je využít Bezoutovu větu. Najdeme a.beZ tak, že 39a + 47b = 1. Pak vynásobíme číslem 41. Řešení je x = 41a. (3) Obvykle nejrychlejší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 (mod 47) -8x = -6 (mod 47) 4x = 3 (mod 47) <=^> 4x = -44 (mod 47) <=^> x = -11 (mod 47) ^> x = 36 (mod 47) Více ve cvičení. 11. přednáška Kongruence 22/29 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 = c\ (mod m,). Dostaneme tak soustavu kongruencí x = c-i (mod at?1 ) ■ ■ ■ x = ck (mod mk) 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í. 11. přednáška Kongruence 23/29 Řešení soustav lineárních kongruencí Věta_ Nechť c-i, c2 jsou celá čísla, m1, m2 přirozená. Označme d = (at?1 . m2). Soustava dvou kongruencí x = (mod at?1 ) x = c2 (mod at?2) v případě c^ ^ c2 (mod oř) nemá řešení. Jestliže naopak d = c2 (mod d), pak existuje celé číslo c tak, že x eZ vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod [m-i, m2]). Má-li soustava nějaké řešení x eZ, platí nutně x = Ci (mod d), x = c2 (mod d), a tedy i c-i = c2 (mod oř). 11. přednáška Kongruence 24/29 Náznak důkazu Předpokládejme dále c-i = c2 (mod d). První kongruenci řešené soustavy vyhovují všechna celá čísla x tvaru x = d + fr7?-|, kde ŕ £ Z je libovolné. Toto x bude vyhovovat i druhé kongruenci soustavy, právě když bude platit d + ř/771 = c2 (mod A7?2), tj. ř/T71 = c2 - c1 (mod m2). Podle věty o řešitelnosti lineárních kongruenci má tato kongruence (vzhledem k t) řešení, neboť d = (m^ m2) dělí c2 - d. 11. přednáška Kongruence 25/29 Čínská zbytková věta 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) Nechť A77-|,,.. a-i,..., a/c g , nik g N jsou po dvou nesoudělná, Pak platí: soustava x = a-i (mod at?1 ) x = a/c (mod mk) má jediné řešení modulo at?1 • m2 -• • mk. Řešení hledáme stejně jako v předchozím důkazu, jak uvidíte v následujícím příkladu. 11. přednáška Kongruence 26/29 Příklad 9 Příklad (9) Řešte systém kongruencí x = 1 (mod10) x = 5 (mod18) x = -4 (mod 25). Řešení: Z první kongruence plyne, že x = 10y + 1. Dosazením do druhé kongruence dostaneme 10y = 4 (mod 18), ekvivalentně 5y = 2 (mod 9). Řešení je y = 9z + 4, proto x = 90z + 41. Dosazením do poslední kongruence dostaneme 90z = -45 (mod 25), ekvivalentně 18z = -9 (mod 5), vydělíme 9 a dostaneme 2z = -1 (mod 5). Tedy z = 5a + 2. Dosazením x = 90(5a + 2) + 41 = 450 + 180 + 41 = 221 (mod 450). Výsledkem je x = 221 (mod 450). 11. přednáška Kongruence 27/29 Příklad 10 Čínskou zbytkovou větu můžeme použít také „v opačném smeru . 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 ^(3564) = 2 • (33 • 2) • 10 = 1080, je řešení tvaru x = 915 • 239411079 (mod 3564). Úprava čísla stojícího na pravé straně by však vyžádala značné úsilí. Proto budeme kongruencí řešit poněkud jinak. 11. přednáška Kongruence 28/29 Dokončení příkladu 10 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) 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. 11. přednáška Kongruence 29/29