Kongruence, rozklad na zbytkové třídy
Kongruence: a,b e Z,m e N,m>2. Platí a = 6(modm) O ml{a-b).
Dávají-li celá čísla a, b po dělení přirozeným číslem m týž zbytek r (OS r < m), řekneme, že
čísla a, b jsou spolu kongruentni podle modulu m._
Vlastnosti kongruencí; Eulcrova funkce; Eulerova věta viz přednáška.
Příklady
1. Určete, zda jsou čísla a,b kongruentni podle modulu m.
a) a = 5, b= 15, m = 4 (ne)
b) a = 3,b = l,m = 2 (ano)
c) a = 7, * = 25, m = 3 (ano)
d) a = 7, b = 25, m = 4 (ne)
2. Nalezněte zbytek po dělení čísla 52c číslem 26. (1)
3. Nalezněte zbjlek po dělení čísla 312' číslem 17. (7)
4. Dokažte, že mezi 82 libovolně zvolenými přirozenými čísly existují dvě, jejichž rozdíl je dělitelný číslem 81.
5. Dokažte, že každé prvočíslo větší než tři lze zapsat ve tvaru 6k + 1 nebo 6k + 5.
6. Dokažte, že 13/(2 60 + 730).
7. Dokažte, že 112/(8355 + ůf -1.
8. Dokažte, že platí: Vn e Ar: 7/(37"*2 +16"+1 + 23").
9. Dokažte, že některý násobek čísla 21 končí na 241.
10. Nalezněte poslední dvě číslice čísla 311'4. (69) Úlohy k procvičení
11. Nalezněte zbytek po dělení čísla 12U4 číslem 65. (1)
12. Pomocí kongruencí dokažte, že 65/(l2136 + 472).
13. Nalezněte zbytek po dělení čísla 210 číslem31. (1)
14. Nalezněte zbytek po dělení čísla 7 1 číslem 144. (55)
1312
15. Určete poslední číslici v dekadickém zápisu čísla 13. (i)
16. Určete poslední číslici v dekadickém zápisu čísla 8 (4)
17. Řešte kongruencí:
a) 12*
b) 14x
c) 72*
d) 29x
7(modl7) 23 (mod31) 2(modl0) 31(mod37)
(xs2(mod17)) (x326(mod31)) (x = l(mod5)) (.X5l0(mod37))