fAígtbra MB104 -jaro 2011 1 Cvičení 1: Teorie čísel Teorie: V prvním cvičení se budeme zabývat teorií čísel. Vše, co se naučíme, budeme využívat i v dalších cvičeních, proto je důležité porozumět základním pojmům. Ze střední školy byste již měli znát pojmy jako dělitelnost, největší společný dělitel, nejmenší společný násobek. Pro osvěžení si uveďme jejich definice. 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. 1 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) 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. Nechť 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_1 = 1 (mod 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 = pl1.....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! - 1iPk- 1)PT1 2 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). Příklad 1. Určete podíl q a zbytek r po dělení čísla a číslem 6 1. a = -47, 6=11 3. a = 47, b = -11 2. a = -47, b = -11 4. a = n3 - 1, 6 = n + 1, n G N 1. a = -5,6 = 8 3. a = -4,6 = 3 2. a = 5,6 = 8 4. a = n2 — n,b = n— 1 Příklad 2. Určete největší společný dělitel čísel a, 6 a určete příslušné koeficienty v Be-zoutově rovnosti 1. a = 21, 6 = 98 2. a = 10175, 6 = 2277 1. 7 = 5 • 21 + (-1) • 98 2. 11 = (-32) • 10175 + 143 • 2277 Příklad 3. Nechť a G Z. Dokažte, že 1. a2 dává po dělení čtyřmi zbytek 0 nebo 1. 2. a4 dává po dělení osmi zbytek 0 nebo 1. Řešeni. 1. Uvažujme a = 2fc + 1 a a = 2A;. Po umocnění dostáváme požadované tvrzení. 2. Použijeme výsledek předchozího příkladu, tedy uvažujme a2 = Ak + 1 a a2 = 4A;. Opět po umocnění dostaneme požadované tvrzení. Příklad 4. Určete všechna celá čísla x tak, aby 3 1. Ax = 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. [67]5i7 2. [172]235 3. [116]i53 4. [49]226 1. [463]5i7 2. [138]235 3. [62]153 4. [143]226 Příklad 6. Určete 1. v?(2010) 2. ^(1212) Uí/s/ede/c. 1. 528 2. 400 Příklad 7. Určete všechna přirozená čísla n taková, že 1. (ra) = 20 3. p(ra) = 11 Uí/s/edeA;. 1.7,9,14,18 2.25,33,44,50,66 3. žádné neexistuje Příklad 8. Určete všechna dvojciferná přirozená čísla n taková, že 91