(DeTtwcvieení
M<B104 -18. 2. 2013
Definice 1. Nechť a, b G Z. Řekneme, že celé číslo a dělí celé číslo b, píšeme a\b, jestliže existuje k G Z tak, že b = a ■ k.
S dělitelností souvisí věta o dělení celých čísel se zbytkem. Tuto větu považujeme za zcela zřejmou. V tomto předmětu si však ukážeme, že ne ve všech okruzích platí.
Věta 1 (O dělení celých čísel se zbytkem). Nechť a, b G Z. Potom existuji q, r G Z taková, že a = b ■ q + r, kde 0 < r < |6|.
Definice 2. Nechť a, b G Z. Řekneme, že celé číslo d je největším společným dělitelem čísel a, b, píšeme d = (a, b), jestliže platí dvě podmínky
1. d\a, d\b
2. Pokud existuje celé číslo c takové, že c\a, c\b, potom c\d.
Největší společný dělitel jste na střední škole určovali Euklidovým algoritmem. Toho budeme využívat i v našem předmětu. S největším společným dělitelem úzce souvisí Be-zoutova identita.
Věta 2 (Bezoutova). Nechť a, b G Z. Potom existuji celá čísla m, n taková, že am + bn = (a,b).
Definice 3. Nechť a, b G Z. Řekneme, že celé číslo n je nejmenším společným násobkem čísel a, b, píšeme n = [a, b], jestliže platí dvě podmínky
1. a\n, b\n
2. Pokud existuje celé číslo m takové, že a\m, b\m, potom n\m.
Nyní se již dostáváme k pojmu kongruence. Tento pojem zřejmě neslyšíte poprvé. Využívali jste ho jistě už v Úvodu do Informatiky či Automatech a gramatikách.
Definujme tedy, kdy jsou spolu dvě celá čísla kongruentní modulo nějaké přirozené číslo.
Definice 4. Nechť a, b G Z, m G N. Řekneme, že a = b (mod m), jestliže a i b dávají stejný zbytek po dělení m.
S definicí kongruence se můžete setkat v několika různých podobách, jak nám říká následující věta.
Věta 3. Nechť a, b G Z; m G 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í věta.
Věta 4. Nechť a,b,c,d G Z, m G N. Nechi a = b (mod m), c = d (mod m). Potom platí
1. a + c = b + d   (mod m)
2. a ■ c = b ■ d   (mod m)
Dále můžeme obě strany kongruence umocnit na stejné přirozené číslo, vynásobit stejným nenulovým celým číslem. Ovšem pozor, nemůžeme obě strany kongruence dělit.
Věta 5 (Malá Fermatova věta). Nechť a G Z, p je prvočíslo takové, že (a,p) = 1. Potom
aP-i — -y   (xaod m).
Relace kongruence modulo přirozené číslo m je relací ekvivalence na množině celých čísel. Uvažme nyní rozklad příslušný této ekvivalenci. Jednotlivým třídám tohoto rozkladu říkáme zbytkové třídy modulo m.
Obsahuje-li zbytková třída modulo m celé číslo a, potom ji značíme [a]m. Zbytkové třídy můžeme sčítat a násobit pomocí reprezentantů. Řekneme, že zbytková třída [b]m je inverzní ke zbytkové třídě [a]m, jestliže [a]m ■ [b]m = [l]m. K výpočtu inverzních tříd využíváme Euklidova algoritmu.
Nyní si řekneme, co je to eulerova funkce.
Definice 5. Funkci ip : N —> N, která každému přirozenému číslu n přiřadí počet přirozených čísel, které jsou menší nebo rovny n a jsou s n nesoudělné, říkáme Eulerova funkce.
To, jak se hodnota Eulerovy funkce počítá, nám řekne další tvrzení.
Věta 6. Nechť a, b jsou dvé nesoudělná přirozená čísla a nechť n = p^1.....pekh je rozklad
přirozeného čísla n na součin prvočísel. Potom
1. ip(a • b) = íp(a) • ip{b)
2. V(n) = (p! - 1(Pk ~ 1)PT1
Věta 7 (Eulerova věta). Nechť a G Z, m G N takové, že (a, m) = 1. Potom
ď{m) = 1   (mod m).
Definice 6. Nechť a G Z, m G N, (a, m) = 1. Řekneme, že řád celého čísla a modulo m je n, jestliže n je nejmenší přirozené číslo takové, že an = 1   (mod m).
Pro řád daného čísla a modulo m platí, že dělí každé takové číslo k, pro které je ak = 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
Příklad 2. Určete [ľT]^1.
Příklad 3. Určete [2k + l]221fe+r
Příklad 4. Určete všechna celá čísla x tak, aby
3rc = 5   (mod 17).
Příklad 5. Určete všechna celá čísla x tak, aby
37x = 82   (mod 105).
Příklad 6. Skupině třinácti pirátů se podařilo uloupit bednu zlatých mincí. Zkusili je rozdělit rovným dílem na třináct hromádek, ale deset mincí jim zbylo. O zbylé mince se strhla rvačka, při níž jednoho piráta propíchli. Přestali tedy bojovat a zkusili mezi sebe znovu rozdělit mince rovným dílem. Tentokrát zbyly tři mince, o které opět začali bojovat. V boji zahynul další pirát a tak si ostatní opět zkusili mince spravedlivě rozdělit, tentokrát úspěšně. Na základě těchto informací určete nejmenší možný počet mincí, které mohla bedna obsahovat.
Příklad 7. Určete ^(735).
Příklad 8. Určete poslední cifru čísla 13 .
Příklad 9. Určete zbytek po dělení čísla2181 + 3181 + 5181 číslem 37.
Příklad 10. Dokažte, že pro všechna prvočísla p větší než 7 platí, že
p36 = 1   (mod 945).
Příklad 11. Určete všechna n G N tak, aby f (n) = ^.
Příklad 12. Určete všechna n G N tak, aby f (n) = 6.
Příklad 13. Určete všechna celá čísla x, y tak, aby
2X = 11 + 7y.
3