®tmocv\ímí
MB104 -jaro 2011
Definice 1. Necht' a,b E Z. Řekneme, ze cele číslo a delí cele číslo b, píseme a\b, jestliže existuje k E Z tak, že b = a • k.
S delitelností souvisí veta o delení celách císel se zbytkem. Tuto vetu považujeme za zcela zrejmou. V tomto predmetu si vsak ukažeme, že ne ve vsech okruzích platí.
Veta 1 (O delení celých císel se zbytkem). Necht a, b E Z. Potom existuji q, r E Z taková, že a = b • q + r, kde 0 < r < \b\.
Definice 2. Necht' a, b E Z. Řekneme, že cele císlo d je nejvetsím spolecním delitelem císel a,b, píseme d = (a,b), jestliže platí dve podmínky
1. d\ a, d\ b
2. Pokud existuje cele císlo c takove, že c\a, c\b, potom c\d.
Nejvetsí spolecní delitel jste na strední skole urcovali Euklidovím algoritmem. Toho budeme využívat i v nasem predmetu. S nejvetsím spolecním delitelem uzce souvisí Be-žoutova identita.
Veta 2 (Bezoutova). Necht a, b E Z. Potom existuji celá čísla m, n taková, že am + bn =
(a, b).
Definice 3. Necht' a, b E Z. Řekneme, že cele císlo n je nejmensím spolecním nísobkem císel a, b, píseme n = [a, b], jestliže platí dve podmínky
1. a\n, b\n
2. Pokud existuje cele císlo m takove, že a\m, b\m, potom n\m.
Nyní se již dostívíme k pojmu kongruence. Tento pojem zrejme neslysíte poprve. Využívali jste ho jiste už v Uvodu do Informatiky ci Automatech a gramatikích.
Definujme tedy, kdy jsou spolu dve celí císla kongruentní modulo nejake pnrožene císlo.
Definice 4. Necht' a, b E Z, m E N. Řekneme, že a = b (mod m), jestliže a i b davají stejní žbytek po delení m.
S definicí kongruence se mužete setkat v nekolika nižních podobach, jak nam ríka nasledující veta.
Veta 3. Necht a, b E Z, m E N. Potom následující podmínky jsou spolu ekvivalentní:
1. a = b   (mod m)
2. m\(a — b)
1
3. Existuje celé číslo k takové, že a = k ■ m + b
To, jak můžeme s kongruencemi pracovat, nám poví následující veta.
Věta 4. Necht a,b,c,d E Z, m E N. Necht a = b (mod m), c = d (mod m). Potom platí
1. a + c = b + d   (mod m)
2. a ■ c = b ■ d   (mod m)
Dale můžeme obe strany kongruence umocnit na stejne prirožene číslo, vynasobit stejnám nenulovám celym císlem. Ovsem pozor, nemůžeme obe strany kongruence delit.
Věta 5 (Mala Fermatova veta). Necht a E Z, p je prvočíslo takove, že (a,p) = 1. Potom
ap~l = 1   (mod m).
Relace kongruence modulo prirožene císlo m je relací ekvivalence na množine celách císel. Uvažme nyní rožklad príslusní teto ekvivalenci. Jednotlivám trídam tohoto rožkladu ríkame žbytkove trády modulo m.
Obsahuje-li žbytková tráda modulo m cele cáslo a, potom ji žnaďme [a]m. Zbytkove trády mužeme scátat a násobit pomocá reprežentantu. RRekneme, že žbytkova tráda [b]m je inveržná ke žbytkove tráde [a]m, jestliže [a]m ■ [b]m = K vypoctu inveržnách trád
využávame Euklidova algoritmu.
Nyná si rekneme, co je to eulerova funkce.
Definice 5. Funkci ^ : N —>• N, ktera každemu priroženemu cáslu n priradá pocet priroženách císel, ktere jsou mensí nebo rovny n a jsou s n nesoudelne, ríkame Eulerova funkce.
To, jak se hodnota Eulerovy funkce pocítá, nám rekne dalsí tvržení.
Věta 6. Necht a, b jsou dve nesoudělná přirozené césla a necht n = p^1pekk je rozklad prirozeneho čísla n na součin prvočísel. Potom
1. ip(a ■ b) = t/?(a) ■ t/?(b)
2. p(n) = (p! - 1)p^1-1(pk - 1)pekk~l
Věta 7 (Eulerova veta). Necht a E Z, m E N takove, Ze (a, m) = 1. Potom
av(m) = 1   (mod m).
Definice 6. Necht' a E Z, m E N, (a, m) = 1. Rekneme, že rad celeho cásla a modulo m je n, jestliže n je nejmensí prirožene císlo takove, že an = 1   (mod m).
Pro rad daneho císla a modulo m platí, že delí každe takove císlo k, pro ktere je a = 1   (mod m).
2
Příklad 1. Určete největší společný dělitel čísel a, b a určete příslušné koeficienty v Be-zoutově rovnosti
1. a = 113, b = 50 2. a = 377 - 1, b = 321 - 1
3
Příklad 2. Určete všechna celá čísla x tak, aby 3x = 5   (mod 17).
4
Příklad 3. Určete zbytek po dělení čísla 1312 + 1211 + ll10 číslem 9.
5
Příklad 4. Dokažte, Ze je číslo 215 + 314 + 513 + 212 delitelne číslem 22.
6
Příklad 5. Určete [17]-1.
7
Příklad 6. Určete [2k + l]-1
22fc+r
s
Příklad 7. Určete ^(735).
9
Příklad 8. Reste kongruenči 4x = S   (mod T).
1o
Příklad 9. Reste soustavu kongruencí
x  =  S   (mod 11) x  =  5   (mod S) x  =   1   (mod 3)
11
Příklad lO. Reste soustavu kongruencí
2T2x  =  T3   (mod 5) 1B2x  =  B3   (mod T) B2x  =   ll3   (mod 9)
l2
Příklad 11. Určete všechna n E N tak, aby ip(n) = 6.
13
1 1 9^
Příklad 12. Určete poslední cifru čísla 13 .
14