MB104 řešené příklady (Kongruence) Jaro 2020
Poznámka. Pro připomenutí, a ≡ b (mod c) znamená, že a, b dávají stejný zbytek po dělení číslem c.
Můžeme tomu rozumět i tak, že c dělí a − b, nebo a = kc + b, pro k ∈ Z.
Kongruence podle téhož modulu můžeme sčítat i odečítat, také násobit. Tedy pro a ≡ b (mod m) a
c ≡ d (mod m) platí
• a + c ≡ b + d (mod m),
• a − c ≡ b − d (mod m),
• ac ≡ bd (mod m).
Obě strany kongruence můžeme umocnit na stejné číslo. Obě strany kongruence můžeme vydělit jejich
společným dělitelem, pokud je to číslo nesoudělné s modulem. Pokud jsou obě strany i modul soudělné, lze
vydělit všechna tři čísla.
Tuto teoretickou výbavu není nutno memorovat, považuji za ideální si ji zkusit na co nejvíce příkladech
a u toho se poučit i o tom, co při kongruencích neplatí. Proto zde předkládám několik vyřešených příkladů
(lineární kongruence a jejich soustavy) jako doplnění komentovaných slidů pana docenta Vokřínka.
Vidíte-li zadání s tím, že tušíte jak to spočítat, zkuste si to prosím nejprve spočítat sami a poté zkontrolovat.
Způsobů řešení a cest k výsledku je spousta.
Příklad 1. Spočtěte 14x ≡ 19 (mod ).
Řešení. Vidíme, že (23, 14) = 1 a samozřejmě 1 | 19, tedy kongruence má právě jedno řešení modulo 23.
1. Mohli bychom obě strany vynásobit 14−1
(mod ). Již víme, že tato inverze existuje.
23 = 1 · 14 + 9
14 = 1 · 9 + 5
9 = 1 · 5 + 4
5 = 1 · 4 + 1
Proto 1 = 5−4 = 5−(9−5) = 2·5−9 = 2(14−9)−9 = 2·14−3·9 = 2·14−3(23−14) = 5·14−3·23.
Máme tedy 5 · 14 − 3 · 23 = 1, z toho plyne 5 · 14 ≡ 1 (mod ).
14x ≡ 19 (mod )
5 · 14x ≡ 5 · 19 (mod )
x ≡ 5 · (−4) ≡ −20 ≡ 3 (mod )
x ≡ 3 (mod )
2. Můžeme využít Eulerovu větu aϕ(n)
≡ 1 (mod n). Víme, že 1422
≡ 1 (mod ).
1421
· 14x ≡ 1421
· 19 (mod )
x ≡ 221
· 721
· (−4) (mod )
x ≡ 26
· 26
· 26
· 23
· (72
)10
· 7 · (−4) (mod )
x ≡ (−5) · (−5) · (−5) · 8 · (3)10
· 7 · (−4) (mod )
x ≡ 25 · 20 · 8 · (33
)3
· 3 · 7 (mod )
x ≡ 25 · 20 · 24 · (4)3
· 7 (mod )
x ≡ 25 · 20 · 24 · (−5) · 7 (mod )
x ≡ 2 · (−3) · 1 · (−5) · 7 (mod )
x ≡ (−6) · (−5) · 7 (mod )
x ≡ 30 · 7 (mod )
x ≡ 7 · 7 (mod )
x ≡ 49 − 2 · 23 ≡ 3 (mod )
x ≡ 3 (mod )
MB104 řešené příklady (Kongruence) Jaro 2020
3. Dalším způsobem je upravování levé i pravé strany pomocí modulu a dělení. Je to snad nejrychlejší
způsob, ale vyžaduje více zkušenosti. Občas to může být na pár řádků, jindy se tento způsob může
až nechutně protáhnout a skoro nevede k výsledku. Může to ovšem posloužit aspoň ke zjednodušení
příkladu. V tomto konkrétním příkladě:
14x ≡ 19 (mod )
14x ≡ (−4) (mod )
7x ≡ (−2) (mod )
7x ≡ (−2) + 23 = 21 (mod )
x ≡ 3 (mod )
4. Poslední uvedený způsob je upravování dvou kongruencí (známo ze slidů), takže jen stručně:
23x ≡ 0 (mod )
14x ≡ 19 (mod )
9x ≡ −19 + 23 = 4 (mod )
5x ≡ 15 (mod )
4x ≡ −11 (mod )
x ≡ 26 ≡ 3 (mod )
0x ≡ −11 − 3 · 4 = −23 ≡ 0 (mod ).
Příklad 2. Spočtěte 37x ≡ 17 (mod ).
Řešení. Předveďme si pouze třetí způsob.
37x ≡ 17 (mod )
10x ≡ −10 (mod )
x ≡ −1 (mod )
x ≡ 26 (mod )
Příklad 3. Spočtěte 13x ≡ 22 (mod ).
Řešení. Lze to spočítat třetím způsobem? Zde už to není tak jednoduché, jako v předchozím příkladě.
Zkuste proto spočítat jiným způsobem.
13x ≡ 22 (mod )
?x ≡? (mod )
Příklad 4. Spočtěte 121x ≡ 250 (mod ).
Řešení. Předveďme si pouze třetí způsob.
121x ≡ 250 (mod )
−39x ≡ 90 (mod )
−13x ≡ 30 (mod )
−13x ≡ 30 − 160 (mod )
−13x ≡ −130 (mod )
x ≡ 10 (mod )
MB104 řešené příklady (Kongruence) Jaro 2020
Příklad 5. Spočtěte 325x ≡ 694 (mod ).
Řešení. Předveďme si třetí způsob. Půjde to?
325x ≡ 694 (mod )
−146x ≡ 694 (mod )
−73x ≡ 347 (mod )
−73x ≡ −124 (mod )
73x ≡ 124 (mod )
Zde už těžko říct jak pokračovat a asi si nevšimneme, že 124 + 25 · 471 je číslo dělitelné 73. Nyní bychom
tedy mohli spočítat inverzi, tedy 73−1
(mod ), nebo upravovat jako dvě rovnice.
471x ≡ 0 (mod )
73x ≡ 124 (mod )
33x ≡ −6 · 124 (mod )
7x ≡ 13 · 124 (mod )
5x ≡ −58 · 124 (mod )
2x ≡ 71 · 124 (mod )
x ≡ (−58 − 2 · 71) · 124 (mod )
x ≡ −200 · 124 (mod )
0x ≡ 471 · 124 ≡ 0 (mod )
Výborně, víme x ≡ −200 · 124 (mod ). To ještě upravíme. (mod ) x ≡ −200 · 124 ≡ −50 · 4 · 124 ≡
−50 · 496 ≡ −50 · 25 ≡ (−20 − 20 − 10) · 25 ≡ −500 − 500 − 250 ≡ −29 − 29 − 250 + 471 ≡ 163. Takže
x ≡ 163 (mod ).
Závěrem si zkusme spočítat ještě jednu soustavu lineárních kongruencí.
Příklad 6. Spočtěte
21x ≡ 27 (mod )
26x ≡ 10 (mod )
27x ≡ 30 (mod )
Řešení. Nejprve zjednodušujeme:
21x ≡ 3 (mod )
x ≡ 10 (mod )
10x ≡ 13 (mod )
Všimneme si, že v první kongruenci jsou obě strany i modul dělitelný třemi. Třetí kongruenci upravíme
snadno, když přičteme modul 17 k pravé straně.
7x ≡ 1 (mod )
x ≡ 10 (mod )
10x ≡ 30 (mod )
MB104 řešené příklady (Kongruence) Jaro 2020
Číslo 7 je jako −1 modulo 8, toho využijeme.
−x ≡ 1 (mod )
x ≡ 10 (mod )
x ≡ 3 (mod )
Ještě jedna úprava prvního řádku.
x ≡ −1 ≡ 7 (mod )
x ≡ 10 (mod )
x ≡ 3 (mod )
Tím jsou přípravné práce hotové. Nyní tedy vidíme, že platí (mějme k, l, m ∈ Z)
x = 7 + 8k.
Dosadíme do druhé kongruence a řešíme pro k:
7 + 8k ≡ 10 (mod )
8k ≡ 3 ≡ 3 + 25 ≡ 28 (mod )
2k ≡ 7 ≡ 7 + 25 ≡ 32 (mod )
k ≡ 16 (mod )
Proto k = 16 + 25l, což dosadíme pro rovnici s x, tedy máme
x = 7 + 8k = 7 + 8(16 + 25l) = 135 + 200l.
Opakujeme postup s třetí kongruencí a řešíme pro l:
135 + 200l ≡ 3 (mod )
135 − (7 · 17) + 200l − (17 · 11)l ≡ 3 (mod )
135 − 119 + (200 − 187)l ≡ 3 (mod )
16 + 13l ≡ 3 (mod )
−1 − 4l ≡ 3 (mod )
−4l ≡ 4 (mod )
l ≡ −1 ≡ 16 (mod )
Proto l = 16 + 17m a opět dosadíme, takže
x = 135 + 200l = 135 + 200(16 + 17m) = 135 + 3200 + 3400m = 3335 + 3400m.
Řešení lze tedy zapsat také x ≡ 3335 (mod ).