Algebra
MB104 -jaro 2011
1   Cvičení 1: Teorie čísel
Teorie: V prvním cvičení se budeme zabývat teorií čísel. Vse, co se naučíme, budeme využívat i v dalsích cvičeních, proto je dUlezite porozumet zýkladním pojmUm. Ze strední skoly byste jiz meli znat pojmy jako delitelnost, nejvetsí spolecní delitel, nejmensí spolecní nísobek. Pro osvezení si uved'me jejich definice.
Definice 1. Necht' a,b E Z. Řekneme, ze cele císlo a delí cele císlo b, píseme a\b, jestlize existuje k E Z tak, ze b = a • k.
S delitelností souvisí veta o delení celích císel se zbytkem. Tuto vetu povazujeme za zcela zrejmou. V tomto predmetu si vsak ukíazeme, ze 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, ze cele císlo d je nejvetsím spolecním delitelem císel a,b, píseme d = (a,b), jestlize platí dve podmínky
1. d\a, d\b
2. Pokud existuje cele císlo c takove, ze c\a, c\b, potom c\d.
Nejvetsí spolecní delitel jste na strední skole urcovali Euklidovím algoritmem. Toho budeme vyuzívat i v nasem predmetu. S nejvetsím spolecním delitelem ízce souvisí Be-zoutova 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, ze cele císlo n je nejmensím spolecním nasobkem císel a, b, píseme n = [a, b], jestlize platí dve podmínky
1. a\n, b\n
2. Pokud existuje cele císlo m takove, ze a\m, b\m, potom n\m.
Nyní se jiz dostavíme k pojmu kongruence. Tento pojem zrejme neslysíte poprve. Vyuzívali jste ho jiste uz v IJvodu do Informatiky ci Automatech a gramatikach.
Definujme tedy, kdy jsou spolu dve cela císla kongruentní modulo nejake prirozene císlo.
Definice 4. Necht' a, b E Z, m E N. Řekneme, ze a = b (mod m), jestlize a i b davají stejní zbytek po delení m.
1
S definicí kongruence se můžete setkat v několika různých podobách, jak nám říká následující veta.
Věta 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)
3. Existuje cele čí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)
Díle můžeme obe strany kongruence umocnit na stejne přirozene císlo, vynasobit stejním nenulovím celym císlem. Ovsem pozor, nemuž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 prirozene 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 žbytkova trída modulo m cele císlo a, potom ji žnacíme [a]m. Zbytkove trídy mužeme sďtat a nísobit pomocí reprežentantu. Rekneme, že žbytkova trída [b]m je inveržní ke žbytkove tríde [a]m, jestliže [a]m • [b]m = K vípoctu inveržních tríd
využívame Euklidova algoritmu.
Nyní si rekneme, co je to eulerova funkce.
Definice 5. Funkci t/? : N —>• N, kterí 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á pnrozena císla a necht n = pe11pekk je rozklad prirozeneho čísla n na součin prvočísel. Potom
1. / (a • b) = / (a) • / (b)
2. /(n) = (p: — (pk — 1)pkfc_1
2
Věta 7 (Eulerova věta). Nechi a E Z, m E N takové, že (a, m) = 1. Potom
ď(m) = 1   (mod m).
Děfinicě 6. Necht' a E Z, m E N, (a, m) = 1. Řekneme, ze rad celěho čísla a modulo m je n, jestliže n je nejmensí pnrozene číslo takove, ze an = 1   (mod m).
Pro rad daneho čísla a modulo m platí, že delí každe takove číslo k, pro ktere je ak = 1   (mod m).
Příklad 1. Určete podíl q a zbytek r po delení čísla a číslem b
1. a = -47, b =11 3. a = 47, b = -11
2. a = -47, b = -11 4. a = n3 - 1, b = n +1, n E N Výsledek.
1. a = -5, b = 8 3. a = -4, b = 3
2. a = 5, b = 8 4. a = n2 - n, b = n - 1
Příklad 2. Určete nejvetsí společný delitel zoutove rovnosti
1. a = 21, b = 98
Výsledek.
1. 7 = 5 • 21+ (-1) • 98
čísel a, b a určete pnslusne koefičienty v Be-
2. a = 10175, b = 2277
2. 11 = (-32) • 10175 + 143 • 2277
Příklad 3. Nechť a E Z. Dokažte, že
1. a2 dava po delení Čtyřmi žbytek 0 nebo 1.
2. a4 dává po delení osmi žbytek 0 nebo 1. Rešeni.
1. Uvažujme a = 2k + 1 a a = 2k. Po umocnení dostávame požadovane ťvřžení.
2. Použijeme vásledek předchožího příkladu, tedy uvažujme a2 = 4k + 1 a a2 = 4k. Opet po umocnení dostaneme požadovane tvřžení.
Příklad 4. Určete vsečhna čela čísla x tak, aby
3
1. 4x = 1 (mod 7) Výsledek.
1. x = 2   (mod 7)
2. 7x = 3   (mod 11)
2. x = 2 (mod 11)
Příklad 5. Určete inverzní zbytkové třídy k zadaným zbytkovým třídám
1.   [67J517 2.   [172]235 3.   [116]i53 4. [49]226
Výsledek.
1. [463]5i7 2. [138]235 3. [62] 153 4. [143]226
Příklad 6. Určete 1. ^(2010)
Výsledek. 1. 528
2. ^(1212)
2. 400
Příklad 7. Určete vsečhna přirozená čísla n taková, Ze
1. p(n) = 6 2. p(n) = 20
Výsledek.
1. 7, 9,14,18 2. 25, 33, 44, 50, 66
3. p(n) = 11
3. žádne neexistuje
Příklad 8. Určete vsečhna dvojčiferna přirozený čísla n takova, ze 9|t/?(n) Výsledek. 19, 27, 37, 38, 54, 57,63, 73, 74, 76, 81,91, 95
Příklad 9. Určete vsečhna prirozena čísla n takova, ze
1. =
2. p(n) =
Nápověda: Napište n jako součin mocniny dvou (resp. tří) a čísla s dvojkou (resp. trojkou) nesoudelneho.
Výsledek.
2
3
4
1. n = 2k
2. n = 2k • 31
Příklad 10. Dokazte, Ze
1. je číslo 260 + 730 delitelne 13.
2. pro libovolne n G N je číslo 722n+2 - 472n + 282ra"1 delitelne číslem 25. Příklad 11. Reste soustavu kongruencí:
x  =  3   (mod 5) x  =  8   (mod 11)
Výsledek. x = — 3   (mod 55)
Příklad 12. Reste soustavu kongruencí:
4x = 3 (mod 7) 5x  =  4   (mod 6)
Výsledek. Nema Tešení.
Příklad 13. Určete zbytek po delení čísla 250 + 350 + 450 číslem 17. Výsledek. 12
Příklad 14. Určete poslední čifru čísla
1. 3579 2 . 3 73737
Výsledek.
1. 3 2. 7
Příklad 15. Určete poslední dve čifry čísla
5
1. 799
2. 141414
Výsledek.
1. 07 2. 36
Příklad 16. Určete zbytek po dělení čísla 533 + 733 číslem 17. Výsledek. 12
Příklad 17. Určete zbytek po delení čísla 2181 + 3181 + 5181 číslem 37. Výsledek. 10
Příklad 18. Dokazte, ze je pro kazde prirozene číslo n číslo 37n+2 + 16ra+1 + 23n delitelne sedmi.
Příklad 19. Určete rád čísla 5 modulo 13. Výsledek. 4
Příklad 20. Určete vsečhna pnrozena čísla n, pro ktera je číslo 3n + 4n — 5n delitelne jedeníačti.
Výsledek. n = 2   (mod 5)
6