Řešení kongruencí o jedné neznámé
Řešené příklady
Příklad. Určete počet řešení a kongruenci vyřešte:
12x  3 (mod 45)
Řešení. d = (12, 45) = 3  3|3. Kongruence tedy je řešitelná, a má právě 3 řešení.
12x  3 (mod 45)
4x  1 (mod 15)
4x  16 (mod 15)
x  4 (mod 15)
x  {45t + 4, 45t + 19, 45t + 34, t  Z}.
Příklad. Řešte soustavu lineárních kongruencí:
x  4 (mod 5)
x  5 (mod 6)
Řešení. x = 6t + 5, t  Z
6t + 5  4 (mod 5)
t  4 (mod 5)
t = 5s + 4, s  Z  x = 30s + 29
x  29 (mod 30)
Příklad. Řešte soustavu kongruencí:
5x + 7y  3 (mod 17)
2x + 3y  -2 (mod 17)
Řešení. Vzhledem k tomu, že obě kongruence jsou vztaženy ke stejnému modulu, lze je
například sčítat. Pokud by kongruence byly vztaženy k různým modulům, bylo by nutné
je před aplikací následujícího postupu upravit tak, aby ke stejnému modulu vztaženy byly.
1
Nejdříve upravíme druhou kongruenci:
2x + 3y  -2 (mod 17)
2x + 20y  -2 (mod 17)
x + 10y  -1 (mod 17)
Tuto upravenou kongruenci přičteme k první kongruenci, čímž se zbavíme jedné z proměn-
ných.
6x + 17y  2 (mod 17)
3x  1 (mod 17)
3x  18 (mod 17)
x  6 (mod 17)
Podobně jako u soustav lineárních rovnic o dvou neznámých, i zde dosadíme nyní již známou
proměnnou x do jedné ze zadaných kongruencí:
2  6 +3y  -2 (mod 17)
12 +3y  -2 (mod 17)
3y  -14 (mod 17)
3y  3 (mod 17)
y  1 (mod 17)
Příklad. Určete primitivní kořeny modulo 23.
Řešení. (23) = 22 = 2  11
g = 2 : 22
 4 (mod 23)
211
 (25
)2
 2  92
 2  9  18  9  (-5)  1
g = 3 : 32
 9 (mod 23)
311
 (33
)3
 32
 43
 9  42
 36  4  2  2  13  8  26  1 (mod 23)
g = 4 : řád 4 = 22
vždy dělí řád 2
g = 5 : 52
 25  2 (mod 23)
511
= (52
)5
 5  25
 5  9  5  45  -1 (mod 23)
Číslo 5 je tedy nejmenším kladným primitivním kořenem modulo 23. Další primitivní kořeny
získáme umocněním čísla 5 na čísla nesoudělná s (23) = 22. Obecně totiž, je-li g řádu
(m), je gn
řádu (m)
(n,(m))
= (m)
1
= (m) a je tedy rovněž primitivním kořenem, kterých je
obecně nekonečně mnoho.
Primitivních kořenů je v redukované soustavě zbytků modulo 23 právě ((23)) = 10.
2
53
 10 (mod 23)
55
 20 (mod 23)
57
 17 (mod 23)
59
 11 (mod 23)
513
 21 (mod 23)
515
 19 (mod 23)
517
 15 (mod 23)
519
 7 (mod 23)
521
 14 (mod 23)
Primitivními kořeny modulo 23 jsou čísla 5, 7, 10, 11, 14, 15, 17, 19, 20, 21.
Příklad. Určete 3
11
.
Řešení. 3
11
= (-1)
3-1
2
 11-1
2  11
3
= (-1) 2
3
= (-1)(-1) = 1
Příklad. Nalezněte všechna x splňující kongruenci x2
 7 (mod 43).
Řešení. Nejdříve pomocí Legenrova symbolu rozhodneme, zda je kongruence řešitelná:
7
43
= (-1)
7-1
2
 43-1
2  43
7
= (-1) 1
7
= (-1)  1 = -1
Kongruence tedy není řešitelná; žádné x, které by ji spňovalo, neexistuje.
Příklad. Vyčíslete Jacobiho symbol 38
165
, a rozhodněte, zda je řešitelná kongruence x2
 38
(mod 165).
Řešení. 38
165
= 2
165
19
165
= 2
3
2
5
2
11
19
3
19
5
19
11
= (-1)
32-1
8  (-1)
52-1
8  (-1)
112-1
8  1
3

-1
5
 2
11
3
= 1
Kongruenci x2
 38 (mod 165) lze zapsat jako soustavu kongruencí:
x2
 38 (mod 3)
x2
 38 (mod 5)
x2
 38 (mod 11),
což je ekvivalentní soustavě
x2
 -1 (mod 3)
x2
 3 (mod 5)
x2
 5 (mod 11).
Z těchto tří kongruencí je řešitelná pouze poslední jmenovaná, celá soustava tak řešení
nemá, a nemá ho ani původní kongruence podle složeného modulu.
3