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 1/29 Osnova 11. přednášky • Kongruence a počítání s nimi a 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. 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), 0,*k#i*h O a = b + mt pro vhodné teZ, !ř> - +i 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 £> = a (mod m)) a tranzitivní (tj. pro každé a,b,ceZza = 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 /Mt/ 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. 1# 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. U Obě strany kongruence i její modul můžeme vydělit jejich I) 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 4ť /l/HSpis /MAS /HA/ Á CL Ojí -JaoO = 2. =• o syuíŕpLs ó // £= 4 /imspO G 4 /^rOS 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 4 i I /hcl (L b . r 1 /ms oil s^f a.-Jb- a 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. •5* S Příklad (1) Nalezněte zbytek po dělení čísla 520 číslem 26. Protože 52 = 25 = -1 (mod 26), platí 520 = (52)io ^,1)10=^ (mod 26)j : ^^^^ a tedy zbytek po dělení čísla 520 číslem 26 je jedna. S1 -i 2-1 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+i dělitelné sedmi. 6n+i + 23" Platí 37 = 16 = 23 = 2^ (mod 7), a tedy podle základních vlastností kongruencí platí k^s^ 37n+2+16n+1 +23" = 2n+2+2n+1+2n = 2"(4+2+1) = 0 (mod 7) Příklad (3) Dokažte, že číslo n = (8355 + 6)18 - 1 je dělitelné číslem 112. | Rozložíme 1J2 =^7 • 16vProtož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 = O, >ŕ-^=(-^f-^=o (mod7) 11. přednáška Kongruence 9/29 Příklad 3 proto 7 | n. Podobně 835 = 3 (mod 16), a tedy 81 +6)18-1 =(3-1 +6)18-1 = 819-1=19-1=0 (mod 16), n= (35 + 6)1B - 1 = (3 ~ " =918-1 = 18 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 -2L = 1 (mod 47)-_í Uéj odečteme 47x = 0, dostaneme x = -6 = 41. Počítáme (mod 47): 39 = -8, proto -8x = 1. Vynásobíme 6 a -v s Sn^fiLíff- v -s -G? s. 41 ***** 14 t 11. přednáška Kongruence 10/29 Příklad 4 Příklad (4) Najdete "inverzi" k číslu 39 modulo 235, tj. najdete x takové, že 39x=1 (mod 235). y é i Protože 235 = 5 • 47_a číslaJ5 a 47 jsou nesoudělná, je kongruence 39x = 1 (mod 235) ekvivalentní se dvěma kongruencemi 3§* s4 C=0 38*54 p9x=1 (mod 47) a(39x = 1 (mod 5) YS* Podle předchozí úlohy má prvá řešení x = A\ (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. 11. přednáška Kongruence 11/29 Y = A4 -i 4 A 4*1 i" Malá Fe r matová 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ť a e Z je takové, že p\ a. Pak ap"1 = 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' n^boť pro všechna k = 1,2,...,p- 1 platí, žep| (P) = kl{P[ky 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 2. 2* = 4 /v^0Í !• fr = d. j/J***.' ) 4c I -M [0 jvnzZ Ár 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í číslq^2148^ bíslenq(47) ] 47 ie 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 =X^f = 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 funkci

(1) = 1,^(5) = 4. if{p) = p-\. 12) = 4, je-li p prvočíslo, je zřejmě 4t2,----fr-fi>»_ 11. přednáška Kongruence 14/29 Výpočet Eulerovy funkce Věta Nechť n e N, jehož rozklad je tvaru n = p"1 • • • pj~k. Pak é (a • fc>) = Věta (Eulerova) Nechť a e Z, m e N, (a, m) = 1. Pa/c (mod m). Definice Nechť a e Z, m e N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší přirozené číslo n splňující a = 1 (mod at?). S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m\ 11. přednáška Kongruence 16/29 Primitivní kořeny To, že je řád definován, plyne z Eulerovy věty - pro každé číslo nesoudělné s modulem je totiž jistě jeho řád nejvýše roven (f(m). Velmi důležitá jsou právě ta čísla, jejichž řád je roven právě (p(m) - tato čísla nazýváme primitivními kořeny modulo JZL Příklad Pro libovolné m e N má číslo 1 modulo m řád 1. Číslo -1 má řád • 1 pro m = 1 nebo m = 2 • 2 pro m > 2 I 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) V/, , (brat cc,i6l 3 Rád Čísla ? mnrlnln 7 jft tpHy rn\/Pn 3 < g ^ V 3*£f 33*É, 3 V= ^, 3r-.T, 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). Pak kongruence (o jedné neznámé x) má řešení právě tehdy, když d | b. Pokud platí d | b, má tato kongruence práve 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 + 3 e Z; k e Z}. Příklad Kongruence 2x = 1 (mod 3) má jedno řešení (modulo 3). O Kongruence IQx = 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 10* = 5 ímorMS^má řešení 2, 3 + 2 = 5, 6 + 2 = 8^9 + 2=^, 12 + 2 = t4 (mod ?5). ^ s ^ Důkaz předchozí věty provedeme pomocí Eulerovy věty: ***** 3 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éfc. ysJ£*2 „r Obráceně dokážeme: pokud d | £>, 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, Ď = d • fr| a m = d • m1. Řešená kongruence je tedy ekvivalentní s kongruencí fij^ =• ^ kde jai.mi) = 1._ b = fe**ť ai • x = ď-i (mod at?1 ) 11. přednáška Kongruence 20/29 Dokončení důkazu Tuto kongruenci můžeme vynásobit číslem á\ Eulerově větě obdržíme (^(A7?1)-1 a díky x^a^-x (mod a771). Tato kongruence má jediné řešení modulo a tedy d = m/m^ řešení modulo m. Ta jsou aif(A7?l)~1 • bj + A:/771, kde /c = 0,1,2,..., d - 1. w 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 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_Naideme a, b e tak, že 39a + 47b = 1. Pak vynásobíme číslem 41. Řešení je(x = 41aj 39 cl ^ 1 au^č (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í. 3 3 • ^j^iS — 4 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 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 = £l (mocl m^) ■ ■ ■ x = (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 = (a77-| 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 q = Co ímod ď>. pak existuje celé číslo c tak, že x e vyhovuje soustavě, právě když vyhovuje kongruencí x = c CfflQd [m^rrteP. | Má-li soustava nějaké řešení x e Z, 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í kongruencí řešené soustavy vyhovují všechna celá čísla x tvaru jĺ = Ci + fr7?i, kde ŕ £ Z je libovolné. Toto x bude vyhovovat i druhé kongruencí soustavy, právě když bude platit d + ř/771 = c2 (mod A7?2), tj. _r/771 = c? -Ci (mod A7?2). Podle věty o řešitelnosti lineárních kongruencí má tato kongruence (vzhledem k ř) řešení, neboť d = (m1, rn2) dělí c2 - c-i. 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-|,,..., mk e N jsou po dvou nesoudělná, a-i,..., ak g Z. Pak platí: soustava x = a-i (mod at?1 ) ■ ■ ■ x = ak (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í 1 (mod 10) 5 (mod 18) 10(^*1 = S- loi 4