MB141 - 11. přednáška Kongruence
Martin Čadek s využitím přednášek pro předmět MB104
Jarní semestr 2022
11. přednáška
Kongruence
1/28
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/28
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 ní).
V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme
a ^ b  (mod ní).
11. přednáška       Kongruence 3/28
Kongruence jako ekvivalence
Lemma
Pro libovolná a,beZ,meN jsou následující podmínky ekvivalentní:
O a = b (mod m),
O a = b + mt pro vhodné t e Z,
Q 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 e Zz 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 A7?) plyne a = c (mod m)) relace, jde tedy o ekvivalenci.
11. přednáška
Kongruence
4/28
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(ř| + t2) a opět podle lemmatu a-i + a2 = fr| + £>2 (mod m). Sečteme-li kongruenci a + £> = c (mod A7?) s kongruencí -£> = -£> (mod m), která zřejmě platí, dostaneme a = c - b (mod m). Sečteme-li kongruenci a = b (mod A7?) s kongruencí mk = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mk = b (mod m).
11. přednáška       Kongruence 5/28
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/28
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 rn2),..., 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 [a7?i ,..., mk]).
• 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/28
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 52U čí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/28
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í
37n+2+1 gn+1 +23n = 2n+2+2n+1 +2n = 2n(4+2+1) = Q    (mod y)
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/28
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/28
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 ap_1 = 1 (mod p).
11. přednáška
Kongruence
12/28
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/28
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 <p(n)= {a g N	3i (f definujeme jako počet celých dělných s n, 0 < a< n, (a, n) = 1}|
Příklad
<£>(1) = 1, (p{5) = 4, </?(12) = 4, je-li p prvočíslo, je zřejmě ifi(p) = p - 1.
11. přednáška       Kongruence 14/28
Výpočet Eulerovy funkce
Věta
Nechť neN, jehož rozklad je tvaru n = p"1 • • • p£k. Pak
ip(n) = p^-'■ ■ ■ Pakk~\p, -1)...(P,-1)
Předchozí výsledek lze obdržet z následujících dvou tvrzení.
• Nechť a, b e N, (a, £>) = 1. Pak <p(a • £>) = <p(a) • <p(Ď). o ^(p«) = pa- p«-1 = (p - 1) • p«-1.
Příklad (6)
Vypočtěte y>(72).
72 = 23 • 32 y>(72) = 72 • (1 - 1) • (1 - J) = 24, alternativně ^(72) = ^(8) • <p(9) = 4 • 6 = 24.
11. přednáška       Kongruence 15/28
Eulerova věta
Věta (Eulerova)	
Nechť a e Z, m e N, (a, m) = 1.	Pa/c
	(mod ni).
S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m\
Definice
Nechť a e Z, m e N (a, m) = 1. Řádem čísla a modulo rn rozumíme nejmenší přirozené číslo n splňující
an = 1    (mod AT?).
11. přednáška       Kongruence 16/28
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 m.
Příklad (7)
Určete rád čísla 2 modulo 7.
j
Řešení:
21 = 2 ž 1   (mod 7)
22 = 4 ^ 1   (mod 7)
23 = 8 = 1   (mod 7)
Řád čísla 2 modulo 7 je tedy roven 3.
11. přednáška
Kongruence
17/28
Lineární kongruence o jedné neznámé
Nechť m e N, a, b e Z. Označme d = (a, m). Pak kongruence
ax = 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).
Ř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
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
18/28
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, Ď = d • fr| a m = d • m1. Ř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 19/28
Dokončení důkazu
Tuto kongruenci můžeme vynásobit číslem ä\ Eulerově větě obdržíme
V?(A7?1)-1
a díky
—  o^(™1 )     xx — 0^(^l)-1
x = a
i
x = a
i
• £>i   (mod A7?i).
Tato kongruence má jediné řešení modulo m1 a tedy d = m/m^
řešení modulo m. Ta jsou a^(A77l)_1 • ď-i + 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
20/28
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 + 47£> = 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 21/28
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 = ci   (mod at?1 )
■
■
■
x = Ck   (mod nik)
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 22/28
Ř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 A772)	
v případě c^ ^ c2 (mod d) 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 [at?1 , A7?2]).	
Má-li soustava nějaké řešení x e Z, platí nutně x = c-i (mod oř), x = c2 (mod oř), a tedy i C1 = c2 (mod oř).
11. přednáška       Kongruence 23/28
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 A7?2). 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
24/28
Čí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ť m-imk e N jsou po dvou nesoudělná, a-i,..., ak e Z. Pak platí: soustava
X = a-|    (mod A77-| )
X = a/c   (mod mk)
má jediné řešení modulo /r?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
25/28
Příklad 9
Příklad (9)	
Řešte systém kongruencí	
x =	1   (mod 10)
x =	5   (mod 18)
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 = 450a + 180 + 41 = 221 (mod 450). Výsledkem je x = 221 (mod 450).
11. přednáška       Kongruence 26/28
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 kongruenci řešit poněkud jinak.
11. přednáška
Kongruence
27/28
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 28/28