Obsah

1 Deliteľnosť v obore celých čísel 3 1.1 Základné pojmy a ich vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Prvočísla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Číselné sústavy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Kongruencie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4.1 Pojem kongruentnosti mod n, základné vlastnosti . . . . . . . . . . . . 14 1.4.2 Použitie kongruencií pri kritériách deliteľnosti prirodzených čísel … 16

1.5 Eulerova funkcia a Eulerova veta . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.5.1 Použitie Eulerovej vety v kryptografii (šifrovaní) . . . . . . . . . . . . 21 1.6 Lineárne kongruencie s jednou neznámou . . . . . . . . . . . . . . . . . . . . 22 1.7 Aritmetické funkcie φ, τ, σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.8 Doplnky. Lagrangeova a Wilsonova veta. . . . . . . . . . . . . . . . . . . . . . 26

2 g-adické rozvoje reálnych čísel. Kritéria iracionálnosti. 29 2.1 g-adický rozvoj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Kritériá racionálnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Úvod

Verzia: 24. septembra 2005

Obsah predmetu

I. Deliteľnosť v obore celých čísel

1. Základné pojmy, najväčší spoločný deliteľ, Euklidov algoritmus, najmenší spoločný násobok.

2. Prvočísla a ich vlastnosti, základná veta aritmetiky, prvočíselná veta.

3. Číselné sústavy, vyjadriteľnosť prirodzeného čísla v g-adickej sústave.

4. Kongruencie, základné vlastnosti relácie kongruentnosti modulo n, použitie kongruencií pri kritériách deliteľnosti prirodzených čísel, Eulerova funkcia, Eulerova veta a jej využitie, lineárne kongruencie s jednou neznámou.

5. Aritmetické funkcie φ, τ, σ a ich vlastnosti.

II. g-adické rozvoje reálnych čísel, kritériá iracionálnosti reálnych čísel

1. Pojem racionálneho a iracionálneho čísla, vyjadriteľnosť reálneho čísla pomocou gadického rozvoja.

2. Periodické g-adické rozvoje, kritérium racionálnosti reálneho čísla vyjadreného v gadickom rozvoji. Ďalšie kritériá racionálnosti ( \sqrt[n]{k}, n, k ∈ ℕ, n ≥ 2; logr, r ∈ ℚ^{+} ).

Kapitola 1

Deliteľnosť v obore celých čísel

1.1 Základné pojmy a ich vlastnosti

Označenia: ℤ = množina všetkých celých čísel ℕ = množina všetkých prirodzených čísel ℕ_{0} = ℕ ∪ {0} V celej kapitole číslo znamená celé číslo.

Definícia 1.1.1. Nech a, b ∈ ℤ. Hovoríme, že a delí b, ak existuje c ∈ ℤ tak, že b = c.a. Označenie: a | b (a ∤ b je negácia a | b).

Príklad. −2 | 6, 2 | −2, 0 | 0, 2 ∤ 3

Veta 1.1.2. Pre ľubovoľné a, b, c ∈ ℤ platí:

(1) a | a

(2) Ak a | b a b | c, tak a | c.

(3) 1 | a

(4) a | 0

(5) b | a ⇔ −b | a ⇔ b | −a ⇔ −b | −a

(6) b | a ⇔ |b| | |a| ⇔ b | |a| ⇔ |b| | a

(7) Ak a | b, tak a.c | b.c.

(8) Ak a.c | b.c a c ≠ 0, tak a | b.

(9) Ak a | b, a | c, tak pre každé d, d′ ∈ Z a | d.b ± d′.c.

(10) Ak a | b a b ≠ 0, tak |a| ≤ |b|.

Dôkaz. (5) Ak b | a, tak existuje c ∈ ℤ, pre ktoré a = c.b. Potom a = (−c).(−b), −c ∈ ℤ, a preto −b | a. Ak −b | a, tak −(−b) | a, a teda b | a. Ostatné ekvivalencie sa dokážu podobne.

(9) Ak a | b a a | c, tak existujú b′, c′ ∈ ℤ pre ktoré b = b′a a c = c′a. Potom db + d′c = db′a + d′c′a = (db′ + d′c′)a, a teda a | db + d′c.

(10) Ak a | b, tak existuje c ∈ ℤ, pre ktoré b = ca. Ak b ≠ 0, tak aj c ≠ 0 aj a ≠ 0, a preto |c| > 0 aj |a| > 0. Pretože |c| > 0, máme 1 ≤ |c|. Potom ale |a| ≤ |c||a| = |ca| = |b|.

Veta 1.1.3 (o delení so zvyškom). Pre každé z ∈ ℤ a každé n ∈ ℕ existuje práve jedna dvojica (k, q) ∈ ℤ × ℤ taká, že z = kn + q a 0 ≤ q < n.

Dôkaz. Existencia. Najprv dokážeme, že veta platí pre každé z ∈ ℕ_{0} a n ∈ N indukciou vzhľadom na z.

Pre z = 0 (k, q) = (0, 0). 0 = 0n + 0, 0 ≤ 0 < n.

Nech tvrdenie platí pre z ≥ 0, dokážeme, že potom platí aj pre z + 1.

Teda platí z = kn + q, 0 ≤ q < n. Potom z + 1 = kn + q + 1. Pretože 0 ≤ q < n, platí 0 < q + 1 ≤ n. Ak q + 1 = n, tak máme z + 1 = (k + 1)n + 0. Ak q + 1 < n, tak máme z + 1 = kn + (q + 1), 0 ≤ q + 1 < n. Teda existencia je dokázaná pre každé z ≥ 0.

Nech teraz z < 0. Potom −z > 0 a teda existuje (k, q) ∈ ℤ × ℤ tak, že −z = kn + q, 0 ≤ q < n. Ak q = 0, tak z = −kn+0, 0 ≤ 0 < n. Ak q > 0, tak q = n−(n−q) a 0 < n−q < n. Potom z = −kn − q = (−k)n − n + (n − q) = (−k − 1)n + (n − q), 0 ≤ n − q < n.

Jednoznačnosť. Nech z = kn + q = k′n + q′, 0 ≤ q < n, 0 ≤ q′ < n. Nech napríklad q′ ≤ q (prípad q ≤ q′ je podobný). Potom q − q′ = (k′ − k)n a teda n | q − q′. Ak q − q′ > 0, tak potom n ≤ q − q′ ≤ q < n - spor. Teda q − q′ = 0, a preto q = q′. Potom (k − k′)n = 0, a preto aj k = k′.

V problematike deliteľnosti v obore celých čísel hrá dôležitú úlohu pojem najväčší spoločný deliteľ.

Definícia 1.1.4. a) Číslo c ∈ ℤ sa nazýva spoločný deliteľ čísel a, b ∈ ℤ, ak c | a a súčasne c | b.

b) Najväčší prvok množiny všetkých spoločných deliteľov čísel a, b sa nazýva najväčší spoločný deliteľ (n.s.d.) čísel a, b. Označenie: d = (a, b).

c) Čísla a, b ∈ ℤ sa nazývajú nesúdeliteľné (súdeliteľné), ak (a, b) = 1 ((a, b) ≠ 1).

Príklad. a) 1 je spoločný deliteľ pre ľubovoľné a, b ∈ ℤ a teda (a, b) ≥ 1.

b) (−4, −6) = 2 a teda −4, −6 sú súdeliteľné.

c) (2, −3) = 1 a teda 2, -3 sú nesúdeliteľné.

d) Pre každé a, b ∈ ℤ (a, b) = (−a, b) = (a, −b) = (−a, −b) = (|a|, |b|).

e) Ak a ≠ 0, tak (0, a) = |a|.

f) Ak a | b a a ≠ 0, tak (a, b) = |a|.

g) (a, b) = (b, a)

h) (0, 0) neexistuje.

Veta 1.1.5. Pre každé a, b ∈ ℤ, pre ktoré a ≠ 0 alebo b ≠ 0, existuje práve jeden najväčší spoločný deliteľ d.

Dôkaz. Nech N_{a,b} = {n ∈ ℕ; n | a a súčasne n | b}. 1 ∈ N_{a,b} a teda N_{a,b} ≠ ∅. Nech napríklad a ≠ 0. Pretože každé n ∈ N_{a,b} delí a, platí n ≤ |a|. Teda N_{a,b} je zhora ohraničená číslom a. Potom ale N_{a,b} má najväčší prvok d, t.j. d = (a, b). Ak (a, b) = d a (a, b) = d′, tak d ≤ d′ a súčasne d′ ≤ d. Teda d′ = d.

V nasledujúcom ukážeme, že existuje metóda pre výpočet najväčšieho spoločného deliteľa pre ľubovoľné a, b ∈ ℤ, a ≠ 0 alebo b ≠ 0. Najprv dokážeme jedno pomocné tvrdenie:

Lema 1.1.6. Nech a, b, c, c′ ∈ ℤ, b ≠ 0 a a = c′b + c. Potom (a, b) = (b, c).

Dôkaz. Nech d = (a, b), d′ = (b, c). Pretože d | a, b a c = a + (−c′)b, platí tiež d | c. Pretože d | b, c, dostávame, že d ≤ d′. Podobne, pretože d′ | b, c a a = c′b + c, platí d′ | a. Pretože d′ | a, b, dostávame d′ ≤ d. Teda d = d′.

Veta 1.1.7 (výpočet najväčšieho spoločného deliteľa). Nech a, b ∈ Z, a ≠ 0 alebo b ≠ 0. Potom platí:

(1) (a) Ak a | b, tak (a, b) = |a|, ak b | a, tak (a, b) = |b|.

(b) Ak a ∤ b a b ∤ a, tak (a, b) vypočítame pomocou Euklidovho algoritmu.

(2) Ak d = (a, b), tak existujú r, s ∈ ℤ také, že

d = ra + sb.

Dôkaz. (1a) Ak a | b a a ≠ 0 alebo b ≠ 0, tak a ≠ 0. Potom zrejme (a, b) = |a|. (|a| | a, b; ak d | a, b, tak d ≤ |a|.)

(2a) Ak (a, b) = |a|, tak |a| = 1a + 0b, ak a > 0, resp. |a| = (−1)a + 0b, ak a < 0. Podobne pre b | a.

(1b) Nech a ∤ b a súčasne b ∤ a. Potom a ≠ 0 aj b ≠ 0 a platí (a, b) = (|a|, |b|). Nech a_{0} = |a|, a_{1} = |b|. Potom a_{0}, a_{1} ∈ ℕ a podľa vety 1.1.3 existujú b_{1}, a_{2} ∈ ℤ tak, že a_{0} = b_{1}a_{1} + a_{2}, 0 < a_{2} < a_{1}; platí tiež (lema 1.1.6)

(a_{0}, a_{1}) = (a_{1}, a_{2}).

Ďalej existujú b_{2}, a_{3} ∈ ℤ tak, že

a_{1} = b_{2}a_{2} + a_{3},  0 ≤ a_{3} < a_{2},  (a_{1}, a_{2}) = (a_{2}, a_{3}).

Ak a_{3} = 0, tak (a_{2}, a_{3}) = a_{2} = (a_{1}, a_{2}) = (a_{0}, a_{1}). Ak a_{3} > 0, tak pokračujeme ďalej. Platí a_{1} > a_{2} > a_{3} > 0. Ak v k-tom kroku dostaneme

a_{k−1} = b_{k}a_{k} + a_{k+1} , 0 ≤ a_{k+1} < a_{k} a a_{k} > 0,

tak existujú b_{k+1} , a_{k+2} tak, že

a_{k} = b_{k+1} a_{k+1} + a_{k+2} , 0 ≤ a_{k+2} < a_{k+1} .

Týmto dostaneme klesajúcu postupnosť a_{1} > a_{2} > … > a_{k} > a_{k+1} > … celých nezáporných čísel, ktorá nemôže byť nekonečná. Preto existuje l ∈ ℕ tak, že a_{l} > 0 a a_{l+1} = 0.

a_{l−2} = b_{l−1}a_{l−1} + a_{l}
a_{l−1} = b_{l}a_{l} + 0.

Potom a_{l} = (a_{l−1}, a_{l}) = (a_{l−2}, a_{l−1}) = … = (a_{2}, a_{1}) = (a_{1}, a_{0}) = (a, b).

Uvedený postup sa nazýva Euklidov algoritmus a posledný nenulový zvyšok v tomto postupe je n.s.d. a, b.

(2) Využijeme Euklidov algoritmus, kde a_{l} = (a_{0}, a_{1}). a_{l} = a_{l−2} + (−b_{l−1})a_{l−1} = a_{l−2} + (−b_{l−1})(a_{l−3} + (−b_{l−2})a_{l−2}) = (−b_{l−1})a_{l−3} + (1 + b_{l−1}b_{l−2})a_{l−2} = … = ua_{0} + va_{1}, u, v ∈ ℤ, teda a_{l} = u|a| + v|b|. Ak a > 0, b > 0, tak a_{l} = ua + vb. Ak a < 0, b > 0, tak a_{l} = (−u)a + vb. Ak a > 0, b < 0, tak a_{l} = ua + (−v)b. Ak a < 0, b < 0, tak a_{l} = (−u)a + (−v)b.

Príklad. a) Určte d = (−819, 792) a nájdite u, v také, že d = u(−819) + v792. |−819| = 819, |792| = 792

819 : 792 = 1  819 = 1.792 + 27

27

792 : 27 = 29  792 = 29.27 + 9

252 9

27 : 9 = 3  (−819, 792) = 9

0

9 = 792 + (−29).27 = 792 + (−29)(810 + (−1)792) = (−29)819 + (1 + 29)792 = 29(−819) + 30.792

b) Vyjadrite číslo \frac{819}{792} v základnom tvare, t.j. v tvare r = \frac{a}{b}, kde (a, b) = 1 a b ≠ 0. (819, 792) = 9, 819 : 9 = 91, 792 : 9 = 88, (91, 88) = 1, \underline{\underline{r = \frac{91}{88}}}

c) Nájdite aspoň jedno celočíselné riešenie rovnice 819x + 792y = 27. 819.(−29) + 792.30 = 9 /.3 819.(−87) + 792.90 = 27 Jedno riešenie je (−87, 90). Popíšeme ako vyzerajú všetky riešenia tejto rovnice. Pre ľubovoľné riešenie platí 819(x + 87) + 792(y − 90) = 0. Označme v = x + 87 a u = y − 90, máme potom 819u + 792v = 0. Predelením 9 dostaneme 88u + 91v = 0, čiže v = −\frac{88}{91} u. Keďže 88 a 91 sú nesúdeliteľné, musí platiť 91 | u, u = 91k. Z toho dostaneme v = −88k. Teda ľubovoľné riešenie má tvar (−87−88k, 90+91k). Množina všetkých riešení je {(−87−88k, 90+91k); k ∈ ℤ}.

Veta 1.1.8. Nech a, b, c ∈ ℤ. Potom platí:

(1) Ak (a, b) = 1 a a | bc, tak a | c.

(2) Ak (a, b) = 1, a | c, b | c, tak ab | c.

(3) Ak (a, b) = 1, (a, c) = 1, tak (a, bc) = 1.

(4) Ak (a, b) = 1, m, n ∈ ℕ, tak (a^{m}, b^{n}) = 1.

(5) Ak (a, b) = d, a = a′d, b = b′d, tak (a′, b′) = 1.

Dôkaz. (1) Existujú u, v ∈ ℤ, pre ktoré 1 = ua + vb a b′ ∈ ℤ, pre ktoré bc = b′a. Potom

c = c(ua + vb) = cua + cvb = cua + vb′a = \underbrace{(cu + vb′)}_{∈ℤ}a. Teda a | c.

(2) Existujú u, v, a′, b′ ∈ ℤ tak, že platí 1 = ua + vb, c = a′a, c = b′b. Potom c = c1 = c(ua + vb) = uac + vbc = uab′b + vba′a = (ub′ + va′)ab. Teda ab | c.

(3) Existujú u, v, u′, v′ ∈ ℤ tak, že 1 = ua + vb, 1 = u′a + v′c. Potom 1 = 1.1 = (ua + vb)(u′a + v′c) = (uu′a + vbu′ + uv′c)a + vv′bc, uu′a + vbu′ + uv′c, vv′ ∈ ℤ. Pre každé d ∈ ℤ platí: ak d | a a d | bc, tak d | 1 (veta 1.1.2(9)), a preto d ≤ |d| ≤ 1. Teda 1 = (a, bc).

(4) Vyplýva z (3), dokáže sa matematickou indukciou. Najprv sa dokáže, že ak (a, b) = 1, tak pre všetky n ∈ ℕ (a, b^{n}) = 1.

(5) Existujú u, v ∈ ℤ d = ua + vb. Potom d = ua′d + vb′d = (ua′ + vb′)d. Pretože d ≠ 0, máme 1 = ua′ + vb′. Pre každé d ∈ ℤ, ak d | a′, d | b′, tak d | 1, a preto d ≤ |d| ≤ 1. Teda (a′, b′) = 1.

Definícia 1.1.9. Nech a, b ∈ ℤ. Číslo c ∈ ℤ sa nazýva spoločný násobok čísel a, b, ak a | c aj b | c. Najmenšie prirodzené číslo n, ktoré je spoločným násobkom a, b sa nazýva najmenší spoločný násobok (n.s.n.) čísel a, b. Označenie: [a, b].

Príklad. [4,6]=[-4,-6]=12 Pre ľubovoľné a, b ∈ ℤ, a ≠ 0, b ≠ 0 platí [a, b] = [|a|, |b|].

Veta 1.1.10.

(1) Nech a, b ∈ ℤ, a ≠ 0, b ≠ 0. Potom existuje práve jedno k ∈ ℕ také, že k = [a, b].

(2) Ak a, b ∈ ℤ, a ≠ 0, b ≠ 0, tak (a, b)[a, b] = |a||b|.

Dôkaz. (1) Nech K_{a,b} = {n ∈ ℕ; a | n a súčasne b | n}. Pretože |a||b| ∈ K_{a,b}, platí K_{a,b} ≠ ∅. Potom ale existuje najmenší prvok k množiny K_{a,b}. Zrejme k = [a, b]. Ak [a, b] = k, [a, b] = k′, tak k ≤ k′ a súčasne k′ ≤ k a teda k = k′.

(2) Označme d = (a, b), k = [a, b]. Existujú a′, b′ ∈ ℤ a = da′, b = db′. Potom (veta 1.1.8(5)) (a′, b′) = 1. Ďalej |a| = d|a′|, |b| = d|b′|, (|a′|, |b′|) = 1.

|a||b| = d|a′|d|b′| = dd|a′||b′|

Stačí teraz overiť, že d|a′||b′| = k. d|a′||b′| = |a||b′| ⇒ |a| | d|a′||b′| ⇒ a | d|a′||b′|. Podobne pre b.

Nech teraz m ∈ ℕ a a | m aj b | m. Potom (pretože d | a) d | m a teda existuje m′ ∈ ℕ také, že m = dm′.

Pretože a | m, máme |a| = d|a′| | m = dm′. Pretože d ≠ 0, máme |a′| | m′.

Podobne sa ukáže, že |b′| | m′. Pretože (|a′|, |b′|) = 1, platí tiež |a′||b′| | m. Potom ale d|a′||b′| | dm′ = m. Teda d|a′||b′| = [a, b] = k.

Príklad. Určte c = [−819, 792]. Vieme, že (−819, 792) = 9. Potom c = \frac{819.792}{9} = 792.91 = 72 072. Teda [−819, 792] = 72 072

Cvičenia

1. Zistite, či pre každé a, b, c ∈ ℤ platí:

a) Ak a | b + c, tak a | b alebo a | c.

b) Ak a | b + c a a | b, tak a | c.

c) Ak a | b.c, tak a | b alebo a | c.

d) Ak a | b, tak a | b.c.

2. Nech a, b ∈ ℤ a existujú u, v ∈ ℤ také, že 1 = ua + vb. Dokážte, že (a, b) = 1.

3. Vypočítajte (a, b) aj [a, b], ak a) a = 6320, b = 3780

b) a = 10111, b = 7365

c) a = 632, b = 642

d) a = 819, b = 792

e) a = 3366, b = 2508

[d) 9, 72072; e) 66,127908]

4. Nájdite všetky prirodzené čísla, ktoré sa škrtnutím poslednej cifry zmenšia štvornásobne (12-násobne).

5. Dokážte, že ak pre každé i = 1, …, n, j = 1, …, m, (a_{i}, b_{j}) = 1, tak (a_{1} … a_{n}, b_{1} … b_{m}) = 1.

6. Nájdite, ak existuje, aspoň jedno celočíselné riešenie rovnice:

a) 193x + 18y = 2, b) 196x + 105y = 84, c) 17x + 21y = 1, d) 196x + 105y = 1

7. Nech a, b, c ∈ ℤ, a ≠ 0 alebo b ≠ 0. Dokážte, že rovnica ax + by = c má aspoň jedno celočíselné riešenie ⇔ (a, b) | c. Ako vyzerá množina všetkých celočíselných riešení takejto rovnice?

8. K dispozícii je 30-litrová nádoba plná vody a 13l a 17l prázdne nádoby. Je možné odmerať 15l?

9. Je daný uhol 19^{∘}. Je možné len pomocou pravítka a kružidla rozdeliť tento uhol na 19 rovnakých častí?

10. Určte počet všetkých prirodzených čísel menších ako 10^{6}, ktoré sú nesúdeliteľné s číslom a) 6, b) 30.

11. a) Dokážte, že ak (a, b) = d, c | a a c | b, tak c | d.

b) Nech (a, b) = d, a = a′c, b = b′c. Potom d = d′c a platí (a′, b′) = d′. Dokážte!

12. Definujte n.s.d. pre tri celé čísla a, b, c (resp. pre a_{1}, …, a_{n}). Dokážte, že ak (a, b, c) označuje n.s.d. a, b, c, tak (a, b, c) = ((a, b), c) = (a, (b, c)).

13. Ak a, b ∈ ℤ, a > 0, b > 0 a \frac{1}{a} + \frac{1}{b} ∈ ℤ, tak a = b a a = 1 alebo a = 2. Dokážte!

14. Dokážte, že pre ľubovoľné c, a, b ∈ ℤ, a ≠ 0 alebo b ≠ 0 platí:

a) Ak b | c, tak (a + c, b) = (a, b).

b) Ak (a, b) = 1, tak (a + b, a − b) = 1 alebo 2.

15. Dokážte, že pre každé a ∈ ℤ je jedno z čísel a, a + 1, a + 2 (a, a + 2, a + 4) deliteľné číslom 3.

16. Ak a, b, c ∈ ℤ a a^{2} + b^{2} = c^{2}, tak a, b nemôžu byť súčasne nepárne.

17. Dokážte: Druhú mocninu každého prirodzeného čísla možno zapísať buď v tvare 4k +1, alebo v tvare 4k.

18. Je pravdivé tvrdenie: Ak ab | c^{2}, tak aspoň jedno z čísel a a b je deliteľom čísla c?

19. Nájdite najväčšieho spoločného deliteľa čísel: a) 2n + 1 a 2n − 1 b) n^{2} − 1 a n^{2} + n, c) n^{3} − 1 a n^{2} − 1, d) n^{3} + 2 a n + 1.

20. Dokážte, že súčin štyroch po sebe idúcich prirodzených čísel je deliteľný 24. 21^{∗}. Dokážte, že ak (a, b) = 1, tak existuje N ∈ ℕ tak, že všetky prirodzené čísla n väčšie

ako N možno zapísať v tvare n = au + bv, kde u, v ∈ ℕ.

1.2 Prvočísla

(Pytagoras 6.stor.p.n.l, Euklides 365-300 p.n.l., Eratostenes 276-194 p.n.l.)

Definícia 1.2.1. Prirodzené číslo p > 1 sa nazýva prvočíslo, ak má práve dva rôzne kladné delitele a to 1 a p (hovoríme im aj triviálne delitele). Číslo m > 1 sa nazýva zložené číslo, ak m nie je prvočíslo, t.j. existuje k ∈ ℕ, 1 < k < m tak, že k | m (ekvivalentne, existujú k, l ∈ ℕ, 1 < k, l < m také, že m = kl).

Príklad. a) 1 nie je ani prvočíslo ani zložené číslo.

b) 2, 3, 5, 7, 11, 13, 17, 19,…, 1 000 000 009 649, 1 000 000 009 651, … sú prvočísla. 2^{216 091} −1= v r. 1985 najväčšie známe prvočíslo, má 65 050 cifier v desiatkovej sústave.

c) 4, 6, 21, každé párne číslo n > 2 sú zložené čísla.

Veta 1.2.2 (Vlastnosti prvočísel). Nech p, q sú prvočísla. Potom platí:

(1) Pre každé a ∈ ℤ, (a, p) = 1 alebo (a, p) = p.

(2) Pre ľubovoľné a, b ∈ ℤ ak p | ab, tak p | a alebo p | b.

(3) Ak p ≠ q, tak (p, q) = 1.

(4) Ak p ≠ q, tak pre každé m, n ∈ ℕ (p^{m}, q^{n}) = 1.

Dôkaz. (1) (a, p) = d ∈ ℕ, d | p, a preto d = 1 alebo d = p.

(2) Nepriamo. Nech p ∤ a a súčasne p ∤ b. Potom (a, p) = 1 aj (b, p) = 1. Potom ale (ab, p) = 1, a preto p ∤ ab.

(3) Vyplýva z (1).

(4) Vyplýva z vety 1.1.8(4).

Veta 1.2.3 (Základná veta aritmetiky). Pre každé n ≥ 2 existuje k ∈ ℕ a prvočísla p_{1}, …, p_{k} tak, že n = p_{1} … p_{k}. Toto vyjadrenie je jednoznačné, až na poradie činiteľov.

Dôkaz. Existencia. Matematickou indukciou 2. typu.

n = 2. Tu k = 1, p_{1} = 2 t.j. 2 = 2 je žiadané vyjadrenie.

Nech n > 2 a výrok platí pre všetky m, 2 ≤ m < n. Ak n je prvočíslo, potom k = 1, p_{1} = n, t.j. n = n je žiadané vyjadrenie. Ak n je zložené číslo, tak existujú m, l ∈ ℕ, 1 < m, l < n také, že n = ml. Pretože 2 ≤ m, l < n, podľa indukčného predpokladu existujú r, s ∈ ℕ a prvočísla p_{1}, …, p_{r}, p_{r+1} , …, p_{r+s} tak, že m = p_{1} … p_{r}, l = p_{r+1} … p_{r+s} . Potom m = p_{1} … p_{r} … p_{r+s} , r+s ∈ ℕ, je požadované vyjadrenie (rozklad), p_{1}, …, p_{r+s} sú prvočísla.

Jednoznačnosť. Opäť indukciou 2. typu.

n = 2. 2 = p_{1} … p_{k}, k ∈ ℕ p_{1}, …, p_{k} sú prvočísla. p_{1} | 2, p_{1} ≠ 1, a preto p_{1} = 2. Ak k > 1, tak dostaneme 1 = p_{2} … p_{k}. Potom p_{2} | 1, a preto p_{2} ≤ 1, čo je spor. Teda k = 1. Dostali sme 2=2.

Nech n > 2 a výrok platí pre všetky m ∈ ℕ, 2 ≤ m < n. Nech n = p_{1} … p_{k} = q_{1} … q_{l}, k, l ∈ ℕ, p_{1}, …, p_{k}, q_{1}, …, q_{k} sú prvočísla. p_{1} | q_{1}, …, q_{l}, a preto existuje i ∈ {1, …, l} p_{1} | q_{i}. Potom p_{1} = q_{i}. p_{1} | n a teda existuje m ∈ ℕ n = p_{1}m.

Nech m = 1. Potom n = p_{1} = q_{1} … q_{i} … q_{l}, p_{1} = q_{i}. Ak l > 1 tak dostaneme 1 = q_{1} … q_{i−1}q_{i+1} … q_{l} > 1, čo je spor. Teda l = 1, q_{i} = q_{1} = p_{1}. Dostali sme n = p_{1} = q_{1}.

Nech m ≥ 2. Potom m = p_{2} … p_{k} = q_{1} … q_{i−1} … q_{i+1} … q_{l}. Podľa indukčného predpokladu je vyjadrenie m jednoznačné, až na poradie činiteľov, t.j. existuje bijektívne zobrazenie σ′: {2, …, k} → {1, …, i − 1, i + 1, …, l} také, že ∀j ∈ {2, …, k} q_{σ′(j)} = p_{j} (zrejme k − 1 = l − 1). Potom ale zobrazenie σ: {1, …, k} → {1, …, l}; σ(1) = i a σ(j) = σ′(j) pre každé j ≥ 2 je bijektívne (a teda k = l) a pre každé j ∈ {1, …, n} q_{σ(j)} = p_{j}. Teda vyjadrenie čísla n je jednoznačné, až na poradie činiteľov.

Dôsledok 1.2.4. Pre každé n ∈ ℕ, n > 1 existuje prvočíslo p také, že p | n.

Príklad. a) 600 = 2.2.2.3.5.5 = 2^{3}.3^{1}.5^{2}, 2 ≠ 3, 5, 3 ≠ 5

b) n ≥ 2 n = p_{1}, …, p_{k} = q_{1}^{k_{1}} … q_{m}^{l_{m}}, q_{1}, …, q_{m} sú navzájom rôzne prvočísla, l_{1}, …, l_{m} ∈ ℕ je kanonický rozklad čísla n na prvočísla.

Veta 1.2.5. Množina všetkých prvočísel je nekonečná.

Dôkaz (Euklides). Nepriamo. Nech p_{1}, …, p_{k}, k ∈ ℕ, sú všetky prvočísla. Utvorme číslo n = p_{1} … p_{k} + 1. Zrejme n > p_{1} … p_{k} > 1, a preto n > 2. Potom existuje prvočíslo p také, že p | n. Pretože p_{1}, …, p_{k} sú všetky prvočísla, existuje i, 1 ≤ i ≤ k také, že p = p_{i}. Teda p_{i} | p_{1} … p_{k}, p_{i} | n, a preto p_{i} | n − p_{1} … p_{k} = 1. Potom p_{i} ≤ 1, čo je spor.

Veta 1.2.6. Nech n = p_{1}^{l_{1}} … p_{k}^{l_{k}} je kanonický rozklad čísla n > 1 a d ∈ ℕ. Potom d | n ⇔ d = p_{1}^{t_{1}} … p_{k}^{t_{k}}, kde pre každé i = 1, …, k je 0 ≤ t_{i} ≤ l_{i}.

Dôkaz. ⇒ Nech d | n. Potom existuje c ∈ ℕ také, že n = c.d. Pretože c.d = p_{1}^{l_{1}} … p_{k}^{l_{k}} a tento rozklad je až na poradie činiteľov jednoznačný, musí platiť c = p_{1}^{s_{1}} … p_{k}^{s_{k}}, d = p_{1}^{t_{1}} … p_{k}^{t_{k}}, kde pre každé i je 0 ≤ s_{i}, 0 ≤ t_{i} a s_{i} + t_{i} = l_{i}. Teda pre každé i je 0 ≤ t_{i} ≤ l_{i}.

⇐ Nech d = p_{1}^{t_{1}} … p_{k}^{t_{k}} a pre každé i = {1, …, k} 0 ≤ t_{i} ≤ l_{i}. Potom pre každé i = {1, …, k} platí l_{i}−t_{i} ≥ 0. Potom c = p_{1}^{l_{1} −t_{1}} … p_{k}^{l_{k}−t_{k}} ∈ ℕ a c.d = p_{1}^{l_{1} −t_{1}} … p_{k}^{l_{k}−t_{k}}.p_{1}^{t_{1}} … p_{k}^{t_{k}} = p_{1}^{l_{1}} … p_{k}^{l_{k}} = n.

Dôsledok 1.2.7. Nech m, n ∈ ℕ a p_{1} … p_{k} sú všetky (navzájom rôzne) prvočísla, ktoré sa vyskytujú v kanonickom rozklade m a n. Potom m = p_{1}^{l_{1}} … p_{k}^{l_{k}}, l_{1} … l_{k} ∈ ℕ_{0}, n = p_{1}^{t_{1}} … p_{k}^{t_{k}}, t_{1} … t_{k} ∈ ℕ_{0} a platí

(m, n) = p_{1}^{s_{1}} … p_{k}^{s_{k}},  kde s_{i} = min{l_{i}, t_{i}} pre i = 1, …, k,
[m, n]= p_{1}^{r_{1}} … p_{k}^{r_{k}},  kde r_{i} = max{l_{i}, t_{i}} pre i = 1, …, k.

Dôkaz. Cvičenie.

Príklad. Určte (5445,2625) aj [5445,2625] Riešenie: 5445 = 3^{2}.5.11^{2} = 3^{2}.5.7^{0}.11^{2} 2625 = 3.5^{3}.7 = 3.5^{3}.7.11^{0} (5445, 2625) = 3.5.7^{0}.11^{0} = 15 [5445, 2625] = 3^{2}.5^{3}.7.11^{2} = 952 875

Veta 1.2.5 hovorí, že prvočísel je nekonečne veľa ale nehovorí o tom, ako sú v množine ℕ rozložené. Pre ľubovoľné x ∈ ℝ nech π(x) je počet všetkých prvočísel, ktoré sú menšie alebo rovné ako x. Potom zrejme π(−1) = π(0) = π(1) = 0, π(2) = 1, π(3) = 2, π(8) = 4 atď. Funkcia π(x) je jednou z možností vyjadrenia rozloženia prvočísel, neexistuje však žiaden vzorec, ktorý by vyjadroval hodnotu π(n) pre každé n ∈ ℕ. Preto bola snaha aproximovať hodnoty funkcie π(x) nejakými elementárnymi funkciami. Jedna z takých funkcií, ktorú navrhol Gauss (18. storočie), je funkcia f(x) = \frac{x}{ln x}. Gauss vyslovil hypotézu, že táto funkcia dobre aproximuje funkciu π(x), t.j. že platí lim_{x→∞} \frac{π(x)}{\frac{x}{ln x}} = 1. Až koncom 19. storočia (1896) sa tento výsledok podarilo dokázať a nazýva sa prvočíselná veta.

Veta 1.2.8 (prvočíselná veta). Nech pre každé x ∈ ℝ π(x) označuje počet všetkých prvočísel menších alebo rovných ako x. Potom

lim_{x→∞} \frac{π(x)}{\frac{x}{ln x}} = 1.

Poznámka. V teórii čísel existuje rad dodnes nevyriešených problémov, známych už viacero storočí. Napríklad je to problém, či prvočíselných dvojčiat je nekonečne veľa alebo len konečný počet (ak p aj p + 2 sú prvočísla, tak dvojica p, p + 2 sa nazýva prvočíselné dvojčatá; napr. 3,5; 5,7; 11,13; …, p= 1 000 000 009 649, p+2.)

Je známe, že pre každé n > 1 existuje prvočíslo p tak, že n < p < 2n. Ďalej je známe, že existuje n_{0} ∈ ℕ tak, že pre každé n ≥ n_{0} existuje prvočíslo p tak, že n^{3} < p < (n + 1)^{3}. Nie je však známe, či podobné tvrdenie platí pre n^{2} a (n + 1)^{2}. Takisto nie je známe, či v postupnosti {n^{2} + 1}_{n=1}^{∞} je konečne alebo nekonečne veľa prvočísel.

Porovnanie hodnôt funkcií π(x) a \frac{x}{ln x} pre niektoré hodnoty x:

\begin{matrix}x & π(x) & \frac{x}{ln x} \\ 1 000 & 168 & 145 \\ 10 000 & 1 229 & 1 086 \\ 100 000 & 9 592 & 8 686 \\ 1 000 000 & 78 498 & 72 382 \\ 10 000 000 & 664 579 & 620 419 \end{matrix}

Cvičenia

1. Dokážte, že ak n ≥ 2 je zložené číslo a p je najmenšie prvočíslo, ktoré delí n, tak p ≤ \sqrt{n}.

2. Zistite, či 283 (397) je prvočíslo.

3. Eratostenovo sito.

4. Nech m > 1. Dokážte, že najmenšie k ∈ ℕ, k > 1, ktoré delí m je prvočíslo.

5. Dokážte, že ak 2^{n} − 1 je prvočíslo (n ∈ ℕ), tak n je prvočíslo. Ukážte, že obrátené tvrdenie neplatí. (M_{n} = 2^{n} − 1 - Mersenovo číslo^{1}) [M_{11} = 2^{11} − 1 = 2047 nie je prvočíslo, 23 | M_{11}.]

6. Dokážte, že ak 2^{n} + 1 (n ∈ ℕ) je prvočíslo, tak existuje m ∈ ℕ_{0} tak, že n = 2^{m}. Ukážte na príklade, že obrátený výrok neplatí. (F_{n} = 2^{2^{n}} + 1 - Fermatove čísla) [F_{5} = 2^{32} + 1 nie je prvočíslo,^{2} 641 | F_{5}.]

7. Dokážte, že pre každé k ∈ ℕ existuje k po sebe nasledujúcich prirodzených čísel, ktoré sú všetky zložené čísla.

8. Dokážte, že pre každé n ∈ ℕ, n > 2 existuje prvočíslo p také, že n < p < n!

9. a) Dokážte, že ak p > 3 je prvočíslo, tak existuje k ∈ ℕ_{0}, pre ktoré p = 6k + 1 alebo p = 6k + 5.

b) Nájdite všetky prvočísla p také, že p + 2 aj p + 10 sú tiež prvočísla.

10. Nech a, b ∈ ℕ, a > 0, b > 0 a a.b = p_{1}^{l_{1}} … p_{k}^{l_{k}} je kanonický rozklad. Potom a = p_{1}^{t_{1}} … p_{k}^{t_{k}}, b = p_{1}^{s_{1}} … p_{k}^{s_{k}}, kde pre každé i 0 ≤ t_{i}, s_{i} ≤ l_{i}. Dokážte, že (a, b) = p_{1}^{u_{1}} … p_{k}^{u_{k}}, kde u_{i} = min{t_{i}, s_{i}} pre všetky i = 1, …, k a [a, b] = p_{1}^{v_{1}} … p_{k}^{v_{k}}, kde v_{i} = max{t_{i}, s_{i}} pre všetky i = 1, …, k.

11. Nájdite kanonické rozklady čísel 4725, 3718, 3234 a určte (4725,3718), [4725,3718], (3718,3234), [3718, 3234].

1mních Mersenne 1644 2Euler 1930

12. Nájdite všetky delitele čísel: a) 72, b) 11^{5}.17^{2}.

13. Nájdite prirodzené číslo, ktoré je deliteľné číslom 2 a číslom 9 a má práve 14 deliteľov v ℕ.

14. Dokážte, že n^{4} + 4 nie je prvočíslo pre n ≥ 2, 5 ∤ n.

15. Zistite, ktoré z uvedených čísel je rovné druhej mocnine nejakého prirodzeného čísla: a) 2^{2}.3^{12}.7^{5}, b) 23^{12}.12^{13}, c) 1234321, d) 157996443.

16. Zistite, koľkými nulami končí číslo a) 100!, b) 1000!

17. Aspoň dvojciferné číslo, ktorého všetky cifry sú rovnaké nie je druhou mocninou žiadneho prirodzeného čísla. Dokážte!

18^{∗}. Nájdite všetky prvočísla tvaru \frac{n(n+1)}{2} − 1, kde n ∈ ℕ.

19. Dokážte, že existuje nekonečne veľa prvočísel tvaru 6k − 1 (k ∈ ℕ).

20. Ak p a p + 2 sú prvočíselné dvojčatá a p > 3, tak 6 | p + 1. Dokážte!

21. Vypočítajte počet deliteľov čísla 324000.

22^{∗}. Koľko čísel menších ako 3^{n}5^{m} je s číslom 3^{n}5^{m} nesúdeliteľných?

23^{∗}. V rovnosti LIK × LIK = BUBLIK nahraďte každé písmeno cifrou tak, aby vznikla identita. (Rôznym písmenám zodpovedajú rôzne cifry.) Riešte tú istú úlohu pre rovnosť SUK × SUK = BARSUK. (Návod: všimnite si, že 1 000 | LIK × (LIK − 1) a čísla LIK a LIK − 1 sú nesúdeliteľné.)

24^{∗}. Dokážte, že ak p je prvočíslo a 0 < n < p, tak p | \binom{p}{n} = \frac{p(p−1)...(p−n+1)}{n!} .

1.3 Číselné sústavy

203 = 2.10^{2} + 0.10 + 3.10^{0} 0 ≤ 2, 0, 3 < 10 203 = 4.7^{2} + 1.7 + 0.7^{0} = (410)_{7} 0 ≤ 4, 1, 0 < 7 13 = 1.2^{3} + 1.2^{2} + 1.2^{0} = (1101)_{2}

Veta 1.3.1. Nech g ∈ ℕ, g ≥ 2. Potom pre každé n ∈ ℕ existuje k ∈ ℕ_{0} a c_{0}, …, c_{k} ∈ ℕ_{0} tak, že pre všetky i ∈ {0, …, k} c_{i} ≤ g −1, c_{k} ≠ 0 a n = c_{k}g^{k} +…+c_{1}g +c_{0}. Toto vyjadrenie je jednoznačné.

Dôkaz. Existencia. Matematickou indukciou. Pre n = 1, k = 0, c_{0} = 1 - platí.

Nech n > 1 a pre všetky m ∈ ℕ, m < n výrok platí. Dokážeme, že potom platí aj pre n. Podľa vety 1.1.3 existujú l, c_{0} ∈ ℤ tak, že

n = l.g + c_{0}, 0 ≤ c_{0} < g.

Zrejme l ≥ 0, pretože ak l < 0, tak l ≤ −1, a preto l.q ≤ −g a potom n = l.g+c_{0} ≤ −g+c_{0} < 0 … spor.

Ak l = 0, máme n = c_{0}, t.j. k = 0, c_{0} ≤ g − 1, c_{0} ∈ ℕ_{0}, c_{0} ≠ 0, t.j. výrok platí.

Nech l ≥ 1. Pretože 1 < g, platí l < l.g ≤ l.g + c_{0} = n. Teda 1 ≤ l < n a podľa indukčného predpokladu existuje k ∈ ℕ_{0}, b_{0}, …, b_{k} ∈ ℕ_{0} tak, že pre všetky i b_{i} ≤ g − 1, b_{k} ≠ 0 a l = b_{k}g^{k} + … + b_{1}g + b_{0}. Potom

n = l.g + c_{0} = b_{k}g^{k+1} + … + b_{0}g + c_{0}.

Ak položíme b_{0} = c_{1}, …, b_{k} = c_{k+1} , tak dostaneme n = c_{k+1} g^{k+1} +…+c_{1}g+c_{0}, (∀i)c_{i} ≤ g−1, c_{k+1} ≠ 0, k + 1 ∈ ℕ_{0}. Teda výrok platí pre n.

Jednoznačnosť. Nech n = c_{k}g^{k} + … + c_{1}g + c_{0} = d_{m}g^{m} + … + d_{1}g + d_{0}, k, m ∈ ℕ_{0}, a pre všetky i 0 ≤ c_{i} ≤ g − 1, c_{k} ≠ 0, pre všetky j 0 ≤ d_{j} ≤ g − 1, d_{m} ≠ 0. Najprv dokážeme, že k = m. Nepriamo. Nech k ≠ m. Potom k < m alebo k > m. Nech k < m. Potom k + 1 ≤ m a

n = c_{k}g^{k} + … + c_{0} ≤ (g − 1)g^{k} + … + (g − 1) =
= (g − 1)(g^{k} + … + 1) = g^{k+1} − 1 < g^{k+1} ≤ g^{m} ≤ d_{m}g^{m} + … + d_{0} = n

Teda n < n … spor. Podobne pre m < k.

Preto k = m.

Nech existuje i také, že c_{i} ≠ d_{i} a j je najväčšie číslo, pre ktoré c_{j} ≠ d_{j}. Nech napríklad c_{j} < d_{j}. Potom

0 = n − n = (d_{j} − c_{j})g^{j} + … + (d_{1} − c_{1})g + (d_{0} − c_{0}) ≥
≥ (d_{j} − c_{j})g^{j} − (g − 1)g^{j−1} − … − (g − 1) ≥ g^{j} − (g^{j} − 1) = 1 > 0.

Teda 0 > 0 … spor. Podobne pre d_{j} < c_{j}.

Preto pre i = 0, …, k c_{i} = d_{i}.

Vyjadrenie n = c_{k}g^{k} + … + c_{1}g + c_{0}, k ∈ ℕ_{0}, c_{0}, …, c_{k} ∈ ℕ_{0}, ∀i c_{i} ≤ g − 1, c_{k} ≠ 0, ktoré zapisujeme tiež n = (c_{k} … c_{0})_{g}, sa nazýva vyjadrenie čísla n v g-adickej sústave.

Príklad. Vyjadrite číslo 356 v sedmičkovej sústave.

356 : 7 = 50  356 = 50.7 + 6

6

50 : 7 = 7  50 = 7.7 + 1
1  356 = (7.7 + 1).7 + 6 = 7^{3} + 1.7 + 6
7 : 7 = 1 < 7  = 1.7^{3} + 0.7^{2} + 1.7 + 6 = (1016)_{7}

0

Vyjadrite 356 v päťkovej sústave.

356 : 5 = 71  71 : 5 = 14  14 : 5 = 2 < 5
1  1  4

356 = (2411)_{5}

Cvičenia

1. Vyjadrite čísla 217, 1513, 2120 v a) 3-kovej, b) 5-kovej, c) 9-kovej sústave.

2. Vyjadrite číslo 12892 v 5-kovej a 6-kovej sústave a číslo (10321)_{4} v desiatkovej sústave. [12892 = (403032)_{5} = (135404)_{6}]

3. Vyjadrite čísla (257)_{8}, (301)_{4} v dvojkovej sústave a čísla (111100101)_{2}, (1100101)_{2} v štvorkovej a osmičkovej sústave.

4. Vyjadrite v dvojkovej sústave prvých 6 prvočísel.

5. Určte číslo n, pre ktoré platí n = (a_{1}a_{0})_{9} = (a_{0}a_{1})_{10}.

6. Určte číslo n, pre ktoré platí n = (a_{1}a_{0})_{10} = (a_{1}a_{0}2)_{3}.

1.4 Kongruencie

1.4.1 Pojem kongruentnosti mod n, základné vlastnosti

Vo vzťahu k deliteľnosti číslom 5 možno množinu ℤ rozdeliť na čísla deliteľné 5 a nedeliteľné 5. Čísla nedeliteľné 5 možno ešte rozdeliť podľa toho, aký zvyšok dávajú po delení číslom 5. Čísla, ktoré dávajú rovnaký zvyšok po delení 5 majú, čo sa týka deliteľnosti číslom 5 rovnaké vlastnosti, budeme hovoriť, že sú kongruentné mod 5.

Definícia 1.4.1. Nech n ∈ ℕ, a, b ∈ ℤ. Hovoríme, že a je kongruentné s b modulo n, ak n | a − b. Zápis: a ≡ b (mod n).

Príklad. 4 ≡ 1 (mod 3), −2 ≡ 3 (mod 5), ∀a, b ∈ ℤ a ≡ b (mod 1)

Veta 1.4.2. Nech a, b, c, d ∈ ℤ a n ∈ ℕ. Potom platí:

(1) a ≡ a (mod n)

(2) Ak a ≡ b (mod n), tak b ≡ a (mod n).

(3) Ak a ≡ b (mod n), b ≡ c (mod n), tak a ≡ c (mod n).

(4) Ak a ≡ b (mod n), c ≡ d (mod n), tak a ± c ≡ b ± d (mod n) a a.c ≡ b.d (mod n).

(5) Al a.c ≡ b.c (mod n), (c, n) = 1, tak a ≡ b (mod n).

(6) Ak f(x) = a_{k}x^{k} + … + a_{1}x + a_{0}, a_{i} ∈ ℤ a c ≡ d (mod n), tak f(c) ≡ f(d) (mod n).

(7) Pre každé a ∈ ℤ existuje práve jedno l ∈ {0, 1, …, n − 1} také, že a ≡ l (mod n).

(8) Ak a = a′n + k, b = b′n + l a 0 ≤ k, l < n, tak a ≡ b (mod n) ⇔ k = l.

(9) Ak a ≡ b (mod n), tak (a, n) = (b, n).

Dôkaz. (1) n | a − a = 0 (2) Ak n | a − b, tak n | −(a − b) = b − a.

(3) Ak n | a − b, n | b − c, tak n | (a − b) + (b − c) = a − c

(4) Ak n | a − b, n | c − d, tak n | (a − b) ± (c − d) = (a ± c) − (b ± d). ac−bd = ac−ad+ad−bd = a(c−d)+d(a−b). Ak n | a−b, n | c−d, tak n | d(a−b)+a(c−d) = ac − bd.

(5) Ak n | ac − bc = (a − b).c, (n, c) = 1, tak n | a − b.

(6) Ak c ≡ d (mod n), tak pre každé i ∈ {1, …, k} c^{i} ≡ d^{i} (mod n). Potom ∀i a_{i}c^{i} ≡ a_{i}d^{i} (mod n), a_{0} ≡ a_{0} (mod n), a preto a_{k}c^{k} + … + a_{1}c + a_{0} ≡ a_{k}d^{k} + … + a_{1}d + a_{0} (mod n).

(7) Existujú k, l ∈ ℤ tak, že a = k.n + l a 0 ≤ l < n, t.j. l ∈ {0, 1, …, n − 1}. Potom a − l = k.n, t.j. n | a − l. Preto a ≡ l (mod n). Nech l′ ∈ {0, 1, …, n − 1} a a ≡ l′ (mod n). Potom l ≡ l′ (mod n) a teda n | l′ − l. Preto n | |l′ − l|. Súčasne 0 ≤ |l′ − l| < n. Preto |l − l′| = 0, t.j. l = l′.

(8) ⇒ Ak a ≡ b (mod n), tak k ≡ l (mod n), lebo platí a ≡ k (mod n) a b ≡ l (mod n).

Pretože k, l ∈ {0, 1, …, n − 1}, máme k = l.

⇐ a ≡ k (mod n), b ≡ l (mod n). Ak k = l, tak a ≡ b (mod n).

(9) n | a − b, (a, n) = d, (b, n) = d′ d | a, n, preto d | a, a − b a potom d | a − (a − b) = b. Teda d | n, b, a preto d ≤ d′. Podobne sa ukáže, že d′ ≤ d.

Uvažujme o kongruentnosti mod 5. Je to relácia ekvivalencie na ℤ. Podľa predchádzajúcej vety, časť (8) platí, že a ≡ b (mod 5) práve vtedy, keď zvyšok po delení čísla a a zvyšok po delení čísla b číslom 5 sú rovnaké. Množina [1]_{5} = {5z + 1; z ∈ ℤ} obsahuje všetky celé čísla, ktorých zvyšok po delení číslom 5 je 1 a teda pre ľubovoľné a, b ∈ [1]_{5} platí a ≡ b (mod 5). Ak c ∉ [1]_{5} a a ∈ [1]_{5}, tak c ≢ a (mod 5).

Analogicky, množiny [0]_{5} = {5z; z ∈ ℤ}, [2]_{5} = {5z + 2; z ∈ ℤ}, [3]_{5} = {5z + 3; z ∈ ℤ}, [4]_{5} = {5z + 4; z ∈ ℤ} sú množiny navzájom kongruentných prvkov mod 5, ktoré sa nazývajú zvyškové triedy mod 5. Ak prvky c, resp. d patria do rôznych zvyškových tried, tak c ≢ d (mod 5). Je zrejmé, že Z = [0]_{5} ∪ [1]_{5} ∪ [2]_{5} ∪ [3]_{5} ∪ [4]_{5} a tieto zvyškové triedy sú navzájom disjunktné. Analogická situácia nastáva pre ľubovoľné n ∈ ℕ.

Definícia 1.4.3. Nech n ∈ ℕ a a ∈ ℤ. Množina [a]_{n} = {c ∈ ℤ; c ≡ a (mod n)} sa nazýva zvyšková trieda modulo n.

Príklad. a) [1]_{5} = {1 + 5z; z ∈ ℤ}, lebo a ≡ 1 (mod 5) ⇔ a − 1 = 5z ⇔ a = 1 + 5z

b) [6]_{5} = {6 + 5z; z ∈ ℤ} = {1 + 5(z + 1); z ∈ ℤ} = [1]_{5}

c) a ∈ [a]_{n}, lebo a ≡ a (mod n).

d) [0]_{n} = {n.z; z ∈ ℤ} - všetky čísla deliteľné n [1]_{n} = {1 + n.z; z ∈ ℤ} - všetky čísla, ktorých zvyšok po delení n je 1 [2]_{n} = {2 + n.z; z ∈ ℤ}

⋮ [n − 1]_{n} = {(n − 1) + n.z; z ∈ ℤ} [n]_{n} = [0]_{n}, [n + 1]_{n} = [1]_{n}, … [−1]_{n} = [n − 1]_{n}, … Zrejme platí [0]_{n} ∪ [1]_{n} ∪ … ∪ [n − 1]_{n} = ℤ.

Veta 1.4.4. Nech n ∈ ℕ, a, b ∈ ℤ. Potom platí:

(1) a ≡ b (mod n) ⇔ [a]_{n} = [b]_{n}

(2) a ≢ b (mod n) ⇔ [a]_{n} ∩ [b]_{n} = ∅

(3) Pre každé a ∈ ℤ existuje k ∈ {0, …, n − 1} tak, že [a]_{n} = [k]_{n}.

Dôkaz. (1) ⇒ Nech c ∈ [a]_{n}. Potom c ≡ a (mod n). Pretože a ≡ b (mod n) dostávame c ≡ b (mod n) a teda c ∈ [b]_{n}. Dokázali sme, že [a]_{n} ⊆ [b]_{n}. Podobne sa ukáže, že [b]_{n} ⊆ [a]_{n}.

⇐ [a]_{n} = [b]_{n} ⇒ b ∈ [a]_{n} ⇒ a ≡ b (mod n).

(2) ⇒ Nech [a]_{n} ∩ [b]_{n} ≠ ∅. Potom existuje c ∈ [a]_{n} ∩ [b]_{n} a teda c ≡ a (mod n), c ≡ b (mod n). Potom a ≡ b (mod n), čo je spor. Teda [a]_{n} ∩ [b]_{n} = ∅.

⇐ Ak a ≡ b (mod n), tak [a]_{n} = [b]_{n} a teda [a]_{n} ∩ [b]_{n} ≠ ∅ (lebo a ∈ [a]_{n} ∩ [b]_{n}).

(3) Pre každé a ∈ ℤ existuje k ∈ {0, …, n−1} tak, že a ≡ k (mod n) (pozri vetu 1.4.2(7)). Teda [a]_{n} = [k]_{n}.

Označme ℤ/mod n = {[a]_{n} : a ∈ ℤ}. Potom ℤ/mod n = {[0]_{n}, [1]_{n}, …, [n − 1]_{n}}. Na tejto množine možno definovať operácie ⊕, ⊙ nasledovne:

[a]_{m} ⊕ [b]_{n} = [a + b]_{n}, [a]_{m} ⊙ [b]_{n} = [a.b]_{n}.

Z vlastnosti 1.4.2(4) vyplýva, že operácie sú definované korektne, t.j. výsledok nezávisí na výbere reprezentantov zvyškových tried. Ľahko sa overí, že platí:

Veta 1.4.5. (a) Pre každé n ∈ ℕ je (ℤ/mod n, ⊕) komutatívna grupa.

(b) Pre každé prvočíslo p je (ℤ/mod p, ⊕, ⊙) pole. Príklad. (ℤ/mod 3, ⊕, ⊙) je pole. [1]_{3} + [2]_{3} = [3]_{3} = [0]_{3} [2]_{3}.[2]_{3} = [4]_{3} = [1]_{3} Vidíme, že toto pole je ţ v podstate� totožné s poľom (Z_{3}, +, ·). Cvičenia

1. Nájdite poslednú cifru čísla a) 213^{174} + 25^{17}, b) 99^{99} + (7^{17})^{17}, c) 127^{37} + 45^{131} + 109^{18}.

2. Nájdite všetky prirodzené čísla n, pre ktoré a) 7 | 2^{n} − 1, b) 7 | 2^{n} + 1.

3. Nech a, b ∈ ℤ. Dokážte, že 19 | 10a + b ⇔ 19 | a + 2b.

4. Overte, či 19 | 539828 s využitím predchádzajúcej úlohy.

5. Nech f(x) = ax^{2} + bx + c, a, b, c ∈ ℤ. Dokážte, že ak f(4) aj f(5) je nepárne číslo, tak rovnica ax^{2} + bx + c = 0 nemá celočíselné korene.

6. Dokážte, že pre každé n ∈ ℕ platí: Ak a_{1}, …, a_{n}, b_{1}, …, b_{n} ∈ ℤ, k ∈ ℕ a pre každé i = 1, …, n a_{i} ≡ b_{i} (mod k), tak a_{1} + … + a_{n} ≡ b_{1} + … + b_{n} (mod k) a a_{1} … a_{n} ≡ b_{1} … b_{n} (mod k).

7. Určte poslednú cifru čísla n = 22.51+698^{5} pri jeho vyjadrení v päťkovej a v sedmičkovej sústave.

8. Ak a, b ∈ ℤ, m, n ∈ ℕ, m | n a a ≡ b (mod n), tak a ≡ b (mod m). Dokážte!

9. Aký je zvyšok 167^{452} po delení 11?

1.4.2 Použitie kongruencií pri kritériách deliteľnosti prirodzených

čísel

Veta 1.4.6. Prirodzené číslo n = c_{k}10^{k} + … + c_{1}10 + c_{0}(= c_{k} … c_{1}c_{0}) je deliteľné číslom 9, resp. 3 ⇔ číslo c_{k} + … + c_{1} + c_{0} je deliteľné číslom 9, resp. 3. Dôkaz.

c_{k} + … + c_{1} + c_{0} = c_{k}1^{k} + … + c_{1}1 + c_{0}

Zoberme polynóm f(x) = c_{k}x^{k} + … + c_{1}x + c_{0}. Zrejme c_{i} ∈ ℕ_{0} ⊆ ℤ. Potom n = f(10), c_{k} + … + c_{1} + c_{0} = f(1). Platí 10 ≡ 1 (mod 9). Potom podľa 1.4.2(6)

n = f(10) ≡ f(1) = c_{k} + … + c_{1} + c_{0} (mod 9).

Potom 9 | n ⇔ 9 | c_{k} + … + c_{1} + c_{0}, lebo čísla kongruentné modulo 9 dávajú pri delení číslom 9 rovnaké zvyšky.

Platí tiež 10 ≡ 1 (mod 3), a preto n = f(10) ≡ f(1) = c_{k} + … + c_{1} + c_{0} (mod 3). Teda 3 | n ⇔ 3 | c_{k} + … + c_{1} + c_{0}.

Príklad. 3 | 149 688 ⇔ 3 | 36 ⇔ 3 | 9 Veta 1.4.7. Číslo n = c_{k}10^{k} + … + c_{1}10 + c_{0}(= c_{k} … c_{1}c_{0}) je deliteľné číslom 11 práve vtedy, keď 11 | c_{0} − c_{1} + c_{2} − … + (−1)^{k}c_{k}

Dôkaz. Využijeme polynóm f(x) = c_{k}x^{k} + … + c_{1}x + c_{0} (c_{i} ∈ ℤ). Zrejme f(10) = n a f(−1) = c_{0} − c_{1} + c_{2} − … + (−1)^{k}c_{k}. Platí 10 ≡ −1 (mod 11), a preto

n = f(10) ≡ f(−1) = c_{0} − c_{1} + c_{2} − … + (−1)^{k}c_{k} (mod 11)

Preto

11 | n ⇔ 11 | c_{0} − c_{1} + c_{2} − … + (−1)^{k}c_{k}.

Príklad. 11 | 25 916 ⇔ 11 | 6 − 1 + 9 − 5 + 2 = 11. Teda 11 | 25916.

Veta 1.4.8. Číslo n = c_{k}10^{k} + … + c_{1}10 + c_{0}(= c_{k} … c_{1}c_{0}) je deliteľné číslom 7, resp. 11 resp. 13 ⇔ číslo 7, resp. 11, resp. 13 delí číslo q = c_{0} + c_{1}10 + c_{2}10^{2} − (c_{3} + c_{4}10 + c_{5}10^{2}) + (c_{6} + c_{7}10 + c_{8}10^{2}) − … = c_{2}c_{1}c_{0} − c_{5}c_{4}c_{3} + c_{8}c_{7}c_{6} − …

Príklad. Pre n = 38 431 252 145 je q = 145−252+421−38 = 286. 286 : 13 = 22, t.j. 13 | 286 ⇒ 13 | n.

Dôkaz. Utvorme polynóm f(x) = (c_{0} + c_{1}10 + c_{2}10^{2}) + (c_{3} + c_{4}10 + c_{5}10^{2})x + (c_{6} + c_{7}10 + c_{8}10^{2})x^{2} + … f(10^{3}) = n, f(−1) = q.

10^{3} ≡ −1 (mod 7),

lebo 10^{3} − (−1) = 1001 = 143.7 = 7.11.13. n = f(10^{3}) ≡ f(−1) = q (mod 7). Preto

7 | n ⇔ 7 | q.

10^{3} ≡ − 1 (mod 11)
n = f(10^{3}) ≡ f(−1) = q (mod 11)
Teda 11 | m ⇔ 11 | q.

Podobne pre 13, pretože 10^{3} ≡ −1 (mod 13).

Príklad. 7 | 10 192 896 ⇔ 7 | 896 − 192 + 10 = 714 7 | 10 192 896

Veta 1.4.9. Nech g ≥ 2 a n = c_{k}g^{k} + … + c_{1}g + c_{0}(= (c_{k} … c_{1}c_{0})_{g}) je prirodzené číslo vyjadrené v g-adickej sústave. Potom platí:

g − 1 | n ⇔ g − 1 | c_{k} + … + c_{0}
g + 1 | n ⇔ g + 1 | c_{0} − c_{1} + … + (−1)^{k}c_{k}

Dôkaz. Využijeme polynóm f(x) = c_{k}x^{k} + … + c_{1}x + c_{0}, n = f(g), c_{k} + … + c_{0} = f(1), c_{0} − c_{1} + … + (−1)^{k}c_{k} = f(−1) a to, že g ≡ 1 (mod g − 1) a g ≡ −1 (mod g + 1).

Cvičenia

1. Dokážte, že číslo n = c_{k}10^{k} + … + c_{1}10 + c_{0} je deliteľné číslom 27, resp. 37 ⇔ 27 resp. 37 delí číslo (c_{0} + c_{1}10 + c_{2}10^{2}) + (c_{3} + c_{4}10 + c_{5}10^{2}) + … = c_{2}c_{1}c_{0} + c_{5}c_{4}c_{3} + …

2. Zistite, či čísla 149 688, 301 587, 10 291 698 sú deliteľné a) číslom 3, resp. 9,

b) číslom 7, 11, resp. 13,

c) číslom 27, resp. 37.

3. Dokážte, že číslo n = c_{k}10^{k} + … + c_{1}10 + c_{0} je deliteľné číslom 101 ⇔ číslo 101 delí číslo (c_{0} + c_{1}10) − (c_{2} + c_{3}10) + (c_{4} + c_{5}10) − … = c_{1}c_{0} − c_{3}c_{2} + c_{5}c_{4} − …

4. Nech p = 10^{m−1} + 10^{m−2} + … + 10 + 1 = \overbrace{11 … 1}^{m cifier} je prvočíslo. Potom aj m je prvočíslo. Ukážte, že obrátené tvrdenie neplatí.

5. Dokážte, že číslo n = c_{k}10^{k} +…+c_{1}10+c_{0} je deliteľné číslom 5 ⇔ c_{0} = 5 alebo c_{0} = 0.

6. Nech n = c_{k}10^{k} + … + c_{1}10 + c_{0}. Dokážte, že platí:

a) 4 | n ⇔ 4 | 10c_{1} + c_{0} (=c_{1}c_{0})

b) 8 | n ⇔ 8 | 10^{2}c_{2} + 10c_{1} + c_{0} (=c_{2}c_{1}c_{0})

7. Zistite, či je číslo (7812)_{9} deliteľné ôsmimi a desiatimi.

8. Zistite, či je číslo (1202)_{6} deliteľné dvomi a tromi.

1.5 Eulerova funkcia a Eulerova veta

Definícia 1.5.1 (Eulerova^{3} funkcia). Zobrazenie φ: ℕ → ℝ, ktoré každému n priradí počet prvkov množiny {k ∈ ℕ; k ≤ n a (k, n) = 1} sa nazýva Eulerova funkcia (teda φ(n) je počet všetkých prirodzených čísel menších alebo rovných ako n, ktoré sú nesúdeliteľné s n.)

Príklad. a) φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(8) = 4

b) Ak n > 1, tak φ(n) je počet všetkých prirodzených čísel menších ako n a nesúdeliteľných s n (lebo (n, n) = n > 1).

c) Pre každé prvočíslo p platí φ(p) = p − 1.

Veta 1.5.2 (Eulerova). Nech n ∈ ℕ. Potom pre každé a ∈ ℤ, pre ktoré (a, n) = 1, platí

a^{φ(n)} ≡ 1 (mod n).

Dôkaz. Nech r_{1}, …, r_{k} sú všetky navzájom rôzne prirodzené čísla také, že pre každé i = 1, …, k 1 ≤ r_{i} ≤ n a (r_{i}, n) = 1. Potom zrejme k = φ(n).

Nech a ∈ ℤ, (a, n) = 1. Potom pre i = 1, …, k (a.r_{i}, n) = 1. Pretože a.r_{i} ∈ ℤ existuje práve jedno l_{i} ∈ {r_{1}, …, r_{k}} také, že a.r_{i} ≡ l_{i} (mod n). Podľa vety 1.4.2(9) (l_{i}, n) = (a.r_{i}, n) = 1. Preto l_{i} ∈ {r_{1}, …, r_{k}} a {l_{1}, …, l_{k}} ⊆ {r_{1}, …, r_{k}}.

Nech i, i′ ∈ {1, …, k} a l_{i} = l_{i′}. Potom ar_{i} ≡ ar_{i′} (mod n) a pretože (a, n) = 1, dostávame r_{i} ≡ r_{i′} (mod n). Pretože 1 ≤ r_{i}, r_{i′} ≤ n, |r_{i} − r_{i′}| ≤ n − 1, a preto r_{i} = r_{i′} a teda i = i′. Teda ak i ≠ i′, tak l_{i} ≠ l_{i′} t.j. {l_{1}, …, l_{k}} má k prvkov, a preto {l_{1}, …, l_{k}} = {r_{1}, …, r_{k}}. Potom l_{1}.l_{2} … l_{k} = r_{1}.r_{2} … r_{k}.

3Euler 1707-1783

Pretože pre každé i = 1, …, k ar_{i} ≡ l_{i} (mod n), podľa vety 1.4.2(4)

ar_{1}.ar_{2} … ar_{k} ≡ l_{1}.l_{2} … l_{k} (mod n),

a teda

a^{k}r_{1}.r_{2} … r_{k} ≡ r_{1}.r_{2} … r_{k} (mod n).

Ak pre všetky i (r_{i}, n) = 1, tak (r_{1}r_{2} … r_{k}, n) = 1, a preto podľa vety 1.4.2(5) a^{k} ≡ 1 (mod n). Teda a^{φ(n)} ≡ 1 (mod n).

Dôsledok 1.5.3. Ak p je prvočíslo, tak pre každé a ∈ ℤ také, že p ∤ a a^{p−1} ≡ 1 (mod p).

Dôkaz. Ak p je prvočíslo, tak φ(p) = p − 1 a (a, p) = 1 ⇔ p ∤ a.

Dôsledok 1.5.4 (Malá veta Fermatova). Ak p je prvočíslo, tak pre každé a ∈ ℤ platí

a^{p} ≡ a (mod p).

Dôkaz. Pre každé a ∈ ℤ platí p | a alebo p ∤ a. Ak p | a, tak a ≡ 0 (mod p) a potom a^{p} ≡ 0^{p} = 0 (mod p). Teda a^{p} ≡ a (mod p).

Ak p ∤ a, tak a^{p−1} ≡ 1 (mod p), a ≡ a (mod p) a teda a^{p} ≡ a (mod p).

Príklad.

1. Dokážte, že pre každé n ∈ ℕ platí, že 15 | n^{5} − n.

Riešenie: n^{5} ≡ n (mod 5), a preto 5 | n^{5} − n.

n^{5} − n = n(n^{4} − 1) = n(n^{2} − 1)(n^{2} + 1) = (n^{3} − n)(n^{2} + 1). n^{3} ≡ n (mod 3), a preto 3 | n^{3} − n a potom 3 | (n^{3} − n)(n^{2} + 1) = n^{5} − n. Teda 5 | n^{5} − n, 3 | n^{5} − n a (3, 5) = 1, a preto 15 = 3.5 | n^{5} − n.

2. Dokážte, že ak p je prvočíslo a a ∈ ℤ také, že p ∤ a (t.j. a ≢ 0 (mod p)), tak existuje b ∈ ℤ také, že a.b ≡ 1 (mod p). Riešenie: a^{p−1} ≡ 1 (mod p), p − 1 ≥ 1. Stačí zobrať b = a^{p−2}. Potom a.b = a.a^{p−2} = a^{p−1} ≡ 1 (mod p).

3. Dokážte, že ak n ∈ ℕ, tak n^{12} je buď deliteľné číslom 13 alebo zvyšok po delení n^{12} číslom 13 je 1. Riešenie: Pretože 13 je prvočíslo, tak 13 | n alebo (n, 13) = 1. Ak 13 | n, tak 13 | n^{12}. Ak (n, 13) = 1, tak podľa Eulerovej vety n^{φ(13)} ≡ 1 (mod 13), t.j. n^{12} ≡ 1 (mod 13). Teda existuje k ∈ ℤ tak, že n^{12} = 13k + 1.

Veta 1.5.5. Ak n > 1 a n = p_{1}^{l_{1}} … p_{k}^{l_{k}} je kanonický rozklad čísla n na prvočísla, tak

φ(n) = n (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{k}} )

Dôkaz. Nech n > 2, n = p_{1}^{l_{1}} … p_{k}^{l_{k}}. Je zrejmé, že ak m ∈ ℕ, tak (m, n) = 1 ⇔ pre všetky i = 1, …, k p_{i} ∤ m_{i}. Teda φ(n) je počet všetkých m ∈ ℕ, ktoré nie sú deliteľné prvočíslami p_{1}, …, p_{k} a pre ktoré m ≤ n. Pre každé j ∈ {1, …, k} označme φ_{p_{1} ,...,p_{j}}(n) počet všetkých tých čísel m ∈ ℕ, pre ktoré m ≤ n a m nie je deliteľné číslami p_{1}, …, p_{j}. Zrejme φ_{p_{1} ,...,p_{k}} = φ(n).

Teraz dokážeme tento výrok: Pre každé n ∈ ℕ, n ≥ 2, platí: Ak n = p_{1}^{l_{1}} … p_{k}^{l_{k}}, p_{1}, …, p_{k} sú navzájom rôzne prvočísla, tak pre každé j ∈ \{1, …, k\} φ_{p_{1} ,...,p_{j}}(n) = n (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j}} ).

Nepriamo. Nech existuje n ∈ ℕ, n ≥ 2, pre ktoré uvedený výrok neplatí. Potom existuje najmenšie prirodzené číslo s touto vlastnosťou. Označme ho n_{0}.

Nech n_{0} = p_{1}^{l_{1}} … p_{k}^{l_{k}}, p_{1}, …, p_{k} sú navzájom rôzne prvočísla, k ≥ 1. Keďže pre n_{0} uvedený výrok neplatí, existuje j ∈ \{1, …, k\} také, že φ_{p_{1} ,...,p_{j}}(n_{0}) ≠ n_{0} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j}} ). Nech j_{0} je najmenšie také číslo.

Uvažujme teraz o φ_{p_{1}}(n_{0}). φ_{p_{1}}(n_{0}) je počet prirodzených čísel m ∈ ℕ, m ≤ n, pre ktoré p_{1} ∤ m. Čísla p_{1}, 2p_{1}, …, \frac{n_{0}}{p_{1}} p_{1} sú všetky kladné násobky p_{1} menšie alebo rovné ako n_{0}, t.j. všetky prirodzené čísla menšie alebo rovné ako n_{0}, ktoré sú deliteľné číslom p_{1}. Ich počet je \frac{n_{0}}{p_{1}} . Preto

φ_{p_{1}}(n_{0}) = n_{0} − \frac{n_{0}}{p_{1}} = n_{0} (1 − \frac{1}{p_{1}} ).

Pre n_{0} a j = 1 výrok platí, a preto j_{0} ≥ 2 a j_{0} − 1 ≥ 1. Z našej voľby j_{0} vyplýva, že

φ_{p_{1} ...p_{j_{0} −1}}(n_{0}) = n_{0} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j_{0} −1}} )

a

φ_{p_{1} ...p_{j_{0}}} (n_{0}) ≠ n_{0} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j_{0}}} )

φ_{p_{1} ...p_{j_{0} −1}}(n_{0}) je počet všetkých tých m ∈ ℕ, m ≤ n_{0}, ktoré nie sú deliteľné p_{1}, …, p_{j_{0} −1}. φ_{p_{1} ...p_{j_{0}}} (n_{0}) dostaneme tak, že do φ_{p_{1} ...p_{j_{0} −1}}(n_{0}) odrátame počet všetkých kladných násobkov čísla p_{j_{0}}, ktoré sú menšie alebo rovné ako n_{0} a ktoré nie sú násobkami čísel p_{1}, …, p_{j_{0} −1}.

Všetky kladné násobky čísla p_{j_{0}}, menšie alebo rovné ako n_{0}, sú 1.p_{j_{0}}, 2.p_{j_{0}}, …, l.p_{j_{0}}, …, \frac{n}{p_{j_{0}}} .p_{j_{0}}, ich počet je \frac{n_{0}}{p_{j_{0}}} . Ak i ∈ \{1, …, j_{0} − 1\}, tak p_{i} | l.p_{j_{0}} ⇔ p_{i} | l, ekvivalentne p_{i} ∤ l.p_{j_{0}} ⇔ p_{i} ∤ l. Pritom 1 ≤ l ≤ \frac{n_{0}}{p_{j_{0}}} .

Teda φ_{p_{1} ,...,p_{j_{0} −1}} (\frac{n_{0}}{p_{j_{0}}} ) je počet tých l, 1 ≤ l ≤ \frac{n_{0}}{p_{j_{0}}} , ktoré nie sú deliteľné žiadnym z čísel p_{1}, …, p_{j_{0} −1}, ktorý je totožný s počtom všetkých kladných násobkov čísla p_{j_{0}}, ktoré sú ≤ n_{0} a nie sú deliteľné žiadnym z čísel p_{1}, …, p_{j_{0} −1}.

Číslo \frac{n_{0}}{p_{j_{0}}} < n_{0} a pretože j_{0} ≥ 2, \frac{n_{0}}{p_{j_{0}}} ≥ p_{1} ≥ 2. Preto platí

φ_{p_{1} ,...,p_{j_{0} −1}} (\frac{n_{0}}{p_{j_{0}}} ) = \frac{n_{0}}{p_{j_{0}}} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j_{0} −1}} ).

Potom

φ_{p_{1} ,...,p_{j_{0}}} (n_{0}) = φ_{p_{1} ,...,p_{j_{0} −1}}(n_{0}) − φ_{p_{1} ,...,p_{j_{0} −1}}(\frac{n_{0}}{p_{j_{0}}} ) =

= n_{0} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j_{0} −1}} ) − \frac{n_{0}}{p_{j_{0}}} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j_{0} −1}} ) =

= n_{0} (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j_{0} −1}} )(1 − \frac{1}{p_{j_{0}}} ).

Tým sme dokázali, že pre každé n ≥ 2 ak n = p_{1}^{l_{1}} … p_{k}^{l_{j}}, tak pre každé j ∈ {1, …, k} φ_{p_{1} ,...,p_{j}}(n) = n (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j}} ). Špeciálne,

φ(n) = φ_{p_{1} ,...,p_{k}}(n) = n (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{j}} ).

1. Dokážte, že platí:

a) 42 | n^{7} − n pre každé n ∈ ℤ,

b) 7 | n^{6k} − 1 pre každé k ∈ ℕ a n ∈ ℤ také, že (n, 7) = 1,

c) n^{13} − n, n ∈ ℤ je deliteľné každým z čísel 2,3,5,7,13.

2. Ak p, q sú prvočísla, p ≠ q, tak pre každé celé číslo a platí: p.q | a^{p.q} − a^{p} − a^{q} + a.

3. Nájdite všetky riešenia rovnice 2^{m} − 3^{n} = 1 v obore prirodzených čísel.

4. Dokážte, že ak n ∈ ℕ a (10, n) = 1, tak existuje k ∈ ℕ tak, že k.n = 99 … 9 - má všetky cifry rovné 9.

5. Dokážte, že pre každé n ∈ ℕ platí:

a) n^{10} = 11k alebo n^{10} = 11k + 1

b) n^{12} = 13k alebo n^{12} = 13k + 1

c) n^{20} = 25k alebo 25k + 1

6. Nech a ∈ ℤ, n ∈ ℕ, (a, n) = 1. Nech k je najmenšie prirodzené číslo, pre ktoré a^{k} ≡ 1 (mod n). Potom pre každé l ∈ ℕ také, že a^{l} ≡ 1 (mod n) platí, že k | l. Špeciálne, k | φ(n). Dokážte!

7. Nájdite najmenšie prirodzené číslo n tak, aby a) 253^{n} ≡ 1 (mod 257)

b) 2^{n} ≡ 1 (mod 257).

8. Dokážte, že ak p, q sú prvočísla a p ≠ q, tak p^{q−1} + q^{p−1} ≡ 1 (mod pq) a p^{q} + q^{p} ≡ p + q (mod pq).

9. Na príklade ukážte, že ak (a, n) > 1, tak nemusí platiť a^{φ(n)} ≡ 1 (mod n).

10. Nájdite najmenšie prirodzené číslo, pre ktoré platí 6x ≡ 1 (mod 35).

11^{∗}. Nájdite najväčší spoločný deliteľ množiny čísel {n^{13} − n, n ∈ ℤ}.

1.5.1 Použitie Eulerovej vety v kryptografii (šifrovaní)

Jedna z metód šifrovania, ktorá sa v súčasnosti používa a je odolná voči odhaleniu je exponenciálna šifra, ktorej podstata je založená na poznatkoch z teórie čísel, vrátane Eulerovej vety.

Nech p je prvočíslo, p > 2 a k je prirodzené číslo, pre ktoré (k, p−1) = 1. Potom existuje q tak, že k.q ≡ 1 (mod (p − 1)), q ∈ {1, …, p − 2}, ktoré možno vypočítať pomocou Euklidovho algoritmu a vety o delení so zvyškom. (Existujú q′, z ∈ ℤ tak, že 1 = q′k + z(p − 1) a existuje q ∈ {0, …, p − 2}, že q′ ≡ q (mod p − 1). Zrejme k.q′ ≡ 1 (mod p − 1) a potom aj k.q ≡ 1 (mod p − 1).)

Ak a ∈ ℤ, 0 < a < p a a^{k} ≡ b (mod p), tak b^{q} ≡ (a^{k})^{q} = a^{k.q} = a^{1+z′(p−1)} = a.(a^{p−1})^{z′} ≡ a (mod p), lebo a^{p−1} ≡ 1 (mod p), pretože p ∤ a.

Ak teda je dané prvočíslo p > 2 a prirodzené číslo k, (k, p − 1) = 1, (k sa nazýva kľúč šifry), a ∈ {1, …, p−2} a poznáme číslo b, pre ktoré b ≡ a^{k} (mod p), tak pomocou k a p vieme určiť q a aj a ≡ b^{q} (mod p), pričom ak 0 < a < p − 2, tak je toto číslo určené jednoznačne.

Príklad. Zašifrujeme (a odšifrujeme) slovo FIRE pomocou prvočísla p = 5801, kľúča k = 61 tak, že text rozdelíme na bloky po 2 písmená, t.j. po 4 cifry. Najprv nahradíme písmená číslami: A → 00, B → 01, C → 02, D → 03, E → 04, F → 05, G → 06, H → 07, I → 08, J → 09, K → 10, L → 11, M → 12, N → 13, O → 14, P → 15, Q → 16, R → 17, …, Z → 25. Teda FIRE prepíšeme na 05081704 a rozdelíme na 2 bloky po 4 cifry (=2 písmená). 0508 1704 Teraz máme

508^{61} ≡ 2713 (mod 5801),  508 < 5801,
1704^{61} ≡ 3726 (mod 5801),  1704 < 5801.

Zašifrovaný text je teda 2713 3726.

Pre odšifrovanie určíme q také, že 61q ≡ 1 (mod 5800), je to číslo q = 1141. Potom určíme, že

2713^{1141} ≡ 508 (mod 5801)
3726^{1141} ≡ 1704 (mod 5801)

a dostaneme pôvodný text 0508 1704, po prepísaní do písmen FIRE.

Táto metóda je značne odolná voči rozlúšteniu šifry pomocou kryptoanalýzy. Aj v prípade, že kryptoanalytik pozná používané prvočíslo p, určenie k pomocou najrýchlejších známych algoritmov vyžaduje pre veľké p veľa času. Napríklad pre 100-ciferné číslo to pre najvýkonnejší počítač (v 80-tych rokoch) vyžadovalo 75 rokov, pre 200-ciferné prvočíslo dokonca 4.10^{9} rokov.

1.6 Lineárne kongruencie s jednou neznámou

Lineárna kongruencia modulo n s jednou neznámou má tvar

a.x ≡ b (mod n),

kde a, b ∈ ℤ, a ≠ 0, n ∈ ℕ a x je neznáma.

Definícia 1.6.1. Zvyšková trieda [c]_{n} modulo n sa nazýva riešením lineárnej kongruencie a.x ≡ b (mod n) ak a.c ≡ b (mod n).

Uvedená definícia je korektná, ak nezávisí od výberu reprezentanta zvyškovej triedy [c]_{n}. Nech [c]_{n} = [d]_{n}. Potom c ≡ d (mod n), a preto aj a.c ≡ a.d (mod n). Teda a.c ≡ b (mod n) ⇔ a.d ≡ b (mod n). Ináč povedané, [c]_{n} je riešenie kongruencie a.x ≡ b (mod n) ⇔ pre každé d ∈ [c]_{n} platí a.d ≡ b (mod n).

Veta 1.6.2. Nech n ∈ ℕ, a, b ∈ ℤ, a ≠ 0 a (a, n) = d. Potom platí:

(1) Kongruencia a.x ≡ b (mod n) má riešenie ⇔ d | b

(2) Ak d | b, tak lineárna kongruencia a.x ≡ b (mod n) má práve d riešení.

Dôkaz. (1) ⇒ Nech [c]_{n} je riešenie danej kongruencie. Potom a.c ≡ b (mod n), a preto n | a.c − b. Pretože d | n, platí aj d | a.c − b a pretože d | a, platí aj d | a.c. Potom d | a.c − (a.c − b) = b.

⇐ Existujú u, v ∈ ℤ tak, že d = u.a + v.n. d | b, preto existuje b′ ∈ ℤ tak, že b = b′d. Potom b = b′d = b′ua + b′vn. Teda a(b′u) − b = (−b′v)n, t.j. n | a(b′u) − b. Potom a.(b′u) ≡ b (mod n) a [b′u]_{n} je riešenie danej kongruencie.

(2) Pretože d | b, existuje riešenie [c_{0}]_{n} danej kongruencie. d | n a preto existuje l ∈ ℕ také, že n = l.d. Položme c_{1} = c_{0} + l, c_{2} = c_{0} + 2l, … c_{d−1} = c_{0} + (d − 1).l. Dokážeme, že [c_{0}]_{n}, [c_{1}]_{n}, …, [c_{d−1}]_{n} sú navzájom rôzne riešenia danej kongruencie a že sú to všetky riešenia. d | a a teda existuje a′ ∈ ℤ tak, že a = a′.d. Pre každé i = 0, …, d − 1 a.c_{i} = ac_{0} + ai.l = ac_{0} + a′idl = ac_{0} + a′.i.n ≡ ac_{0} (mod n), a preto a.c_{i} ≡ b (mod n).

Teda pre každé i = 0, …, d − 1 [c_{i}]_{n} je riešenie a.x ≡ b (mod n). Nech 0 ≤ i < j ≤ d − 1. Potom 0 < c_{j} − c_{i} = (j − i)l ≤ jl < dl = n, a preto n ∤ c_{j} − c_{i}. Teda c_{i} ≢ c_{j} (mod n), t.j. [c_{i}]_{n} ≠ [c_{j}]_{n}.

Nech [c]_{n} je riešenie danej kongruencie. Potom a.c ≡ b (mod n) a preto a.c ≡ a.c_{0} (mod n). Potom n = l.d | a.c − a.c_{0} = a′.d(c − c_{0}). Potom l | a′(c − c_{0}). Ale (a′, l) = 1, a preto l | c − c_{0}. Potom existuje z ∈ ℤ c = c_{0} + zl. Podľa vety o delení so zvyškom existujú s, j ∈ ℤ tak, že z = d.s + j a 0 ≤ j ≤ d − 1. Potom c = c_{0} + jl + sdl = c_{0} + jl + sn ≡ c_{0} + jl = c_{j} (mod n). Teda existuje j ∈ {0, …, d − 1} tak, že [c_{i}]_{n} = [c_{j}]_{n}.

Príklad. 1. Vyriešte lineárnu kongruenciu 20x ≡ 28 (mod 12). Riešenie. (20,12)=4, 4 | 28 a teda existujú práve 4 riešenia.

4 = (−1).20 + 2. 12 /.7
20(−7) + 14.12 = 28
20(−7) ≡ 28(mod 12)

c_{0} = −7, c_{1} = −7 + 3 = −4, c_{2} = −7 + 2.3 = −1, c_{3} = −7 + 3.3 = 2 Riešenia sú [−7] = [5], [−4] = [8], [−1] = [11], [2]. Pretože 20x ≡ 8x (mod 12) a 28 ≡ 4 (mod 12), je daná kongruencia ekvivalentná s kongruenciou 8x ≡ 4 (mod 12).

2. Vyriešte kongruenciu 15x ≡ −66 (mod 18). (15,18)=3, 3 | −66 kongruencia má 3 riešenia.

−66 ≡ 6(mod 18)
15x ≡ 6(mod 18)
3 = (−1).15 + 1.18
15.(−2) + 2.18 = 6
15.(−2) ≡ 6(mod 18)

[-2]=[16] je riešenie. 18 : 3 = 6, ďalšie riešenia sú [4] a [10].

Cvičenia

1. Vyriešte lineárne kongruencie s jednou neznámou:

a) 10x ≡ 14 (mod 12)

b) 7x ≡ 46 (mod 21)

c) 15x ≡ −72 (mod 18)

d) 14x ≡ −63 (mod 35)

2. Zistite, ktoré z nasledujúcich kongruencií sú riešiteľné: a) 6x ≡ 1 (mod 9), b) 9x ≡ 3 (mod 6), c) 14x ≡ 21 (mod 70).

3. Riešte kongruencie: a) 20x ≡ 4 (mod 30), b) 20x ≡ 30 (mod 4), c) 353x ≡ 254 (mod 400).

4. Do kongruencie 10x ≡ 15 (mod n) doplňte za n také číslo, aby: a) kongruencia nemala riešenie,

b) kongruencia mala práve 2 riešenia.

1.7 Aritmetické funkcie φ, τ, σ

Definícia 1.7.1. (1) Ľubovoľné zobrazenie f: ℕ → ℝ sa nazýva aritmetická funkcia.

(2) Aritmetická funkcia f: ℕ → ℝ sa nazýva multiplikatívna, ak platí:

(a) Existuje n ∈ ℕ tak, že f(n) ≠ 0.

(b) Ak m, n ∈ ℕ a (m, n) = 1, tak f(m.n) = f(m).f(n),

Príklad. Eulerova funkcia φ je aritmetická funkcia a ukážeme, že je multiplikatívna.

Funkcia π: ℕ → ℝ, π(n) je počet všetkých prvočísel menších alebo rovných ako n je aritmetická funkcia, nie je multiplikatívna. π(2) = 1, π(3) = 2, π(6) = 3, (2, 3) = 1, 6 = 2.3, 3 = π(6) ≠ π(2).π(3) = 2

Lema 1.7.2. Ak f je multiplikatívna aritmetická funkcia, tak f(1) = 1.

Dôkaz. Existuje n ∈ ℕ, f(n) ≠ 0. (1, n) = 1. 1.f(n) = f(1.n) = f(1).f(n). Preto f(1) = 1.

Definícia 1.7.3. Pre každé n ∈ ℕ τ(n) označuje počet všetkých kladných deliteľov čísla n a σ(n) súčet všetkých kladných deliteľov čísla n.

Príklad. τ(1) = 1, τ(2) = 2, τ(8) = 4, pre každé prvočíslo p τ(p) = 2.

σ(1) = 1, σ(2) = 3, σ(8) = 15, pre každé prvočíslo p σ(p) = p + 1.

τ, σ: ℕ → ℝ sú aritmetické funkcie.

Veta 1.7.4. Nech n ∈ ℕ, n > 1 a n = p_{1}^{l_{1}} … p_{k}^{l_{k}} je kanonický rozklad čísla n na prvočísla. Potom platí:

(1) τ(n) = (l_{1} + 1) … (l_{k} + 1)

(2) σ(n) = \frac{p_{1}^{l_{1} +1} −1}{p_{1} −1} · · · · · \frac{p_{k}^{l_{k}+1} −1}{p_{k}−1} = (p_{1}^{l_{1}} + p_{1}^{l_{1} −1} + … p_{1} + 1) … (p_{k}^{l_{k}} + p_{k}^{l_{k}−1} + … p_{k} + 1)

Dôkaz. (1) d | n ⇔ d = p_{1}^{t_{1}} … p_{k}^{t_{k}}, kde 0 ≤ t_{i} ≤ l_{i} pre i = 1, …, k. Teda τ(n) = (t_{1} + 1) … (t_{k} + 1).

(2) (p_{1}^{l_{1}} + p_{1}^{l_{1} −1} + … p_{1} + 1)(p_{2}^{l_{2}} + p_{2}^{l_{2} −1} + … p_{2} + 1) … (p_{k}^{l_{k}} + p_{k}^{l_{k}−1} + … p_{k} + 1) =

∑_{0≤t_{i}≤l_{i}} p_{1}^{t_{1}} … p_{k}^{t_{k}} = ∑_{d|n} d = σ(n)

Veta 1.7.5. Funkcie φ, τ, σ sú multiplikatívne.

Dôkaz. φ(1) = τ(1) = σ(1) = 1, t.j. pre 1 ∈ ℕ je φ(1) ≠ 0, τ(1) ≠ 0 σ(1) ≠ 0.

Nech m, n ∈ ℕ, (m, n) = 1. Ak m = 1, tak pre každé f ∈ {φ, τ, σ} platí:

f(1.n) = f(n) = 1.f(n) = f(1).f(n).

Podobne pre n = 1.

Nech m > 1 aj n > 1. Potom m = p_{1}^{l_{1}} … p_{k}^{l_{k}}, n = q_{1}^{r_{1}} … q_{s}^{r_{s}}, p_{1}, …, p_{k} aj q_{1}, …, q_{s} sú navzájom rôzne prvočísla. Pretože (m, n) = 1, {p_{1}, …, p_{k}} ∩ {q_{1}, …, q_{s}} = ∅ a teda p_{1}, …, p_{k}, q_{1}, …, q_{s} sú navzájom rôzne prvočísla a m.n = p_{1}^{l_{1}} … p_{k}^{l_{k}}q_{1}^{r_{1}} … q_{s}^{r_{s}} je kanonický rozklad čísla m.n na prvočísla.

Podľa vety 1.5.5

φ(m.n) = m.n (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{k}} )(1 − \frac{1}{q_{1}} )… (1 − \frac{1}{q_{s}} ) =

= m (1 − \frac{1}{p_{1}} )… (1 − \frac{1}{p_{k}} ).n (1 − \frac{1}{q_{1}} )… (1 − \frac{1}{q_{s}} ) = φ(m).φ(n)

Podľa vety 1.7.4 τ(m.n) = (l_{1} + 1) … (l_{k} + 1)(r_{1} + 1) … (r_{s} + 1) = τ(m).τ(n) σ(m.n) = (p_{1}^{l_{1}} + p_{1}^{l_{1} −1} + … + p_{1} + 1) … (p_{k}^{l_{k}} + p_{k}^{l_{k}−1} + … + p_{k} + 1)(q_{1}^{r_{1}} + q_{1}^{r_{1} −1} + … + q_{1} +

1) … (q_{s}^{r_{s}} + q_{s}^{r_{s}−1} + … + q_{s} + 1) = σ(m).σ(n)

Veta 1.7.6. Pre Eulerovu funkciu φ platí:

∑_{d|n} φ(d) = n.

Dôkaz. n = 1. ∑_{d|1}φ(d) = φ(1) = 1.

Nech n > 1, n = p_{1}^{l_{1}} … p_{k}^{l_{k}} je kanonický rozklad n. d | n ⇔ d = p_{1}^{t_{1}} … p_{k}^{t_{k}}, 0 ≤ t_{i} ≤ l_{i}. Pretože ak i ≠ j, tak (p_{i}^{t_{i}}, p_{j}^{t_{j}}) = 1,

φ(d) = φ(p_{1}^{t_{1}}) … φ(p_{k}^{t_{k}}).

Potom

∑_{d|n} φ(d) = ∑_{0≤t_{i}≤l_{i}} φ(p_{1}^{t_{1}} … p_{k}^{t_{k}}) = ∑_{0≤t_{i}≤l_{i}} φ(p_{1}^{t_{1}}) … φ(p_{k}^{t_{k}}) =

= (1 + φ(p_{1}) + … + φ(p_{1}^{l_{1}}))(1 + φ(p_{2}) + … + φ(p_{2}^{l_{2}})) … (1 + φ(p_{k}) + … + φ(p_{k}^{l_{k}})).

Pre každé prvočíslo p a l ∈ ℕ φ(p^{l}) = p^{l} − p^{l−1}, lebo p, 2p, …, p^{l−1}p sú všetky čísla deliteľné p, ktoré sú menšie alebo rovné p^{l} a ich počet je p^{l−1}. Potom

∑_{d|n} φ(d) = (1 + (p_{1} − 1) + (p_{1}^{2} − p_{1}) + … + (p_{1}^{l_{1}} − p_{1}^{l_{1} −1})).
(1 + (p_{2} − 1) + (p_{2}^{2} − p_{2}) + … + (p_{2}^{l_{2}} − p_{2}^{l_{2} −1})) …
…(1 + (p_{k} − 1) + (p_{k}^{2} − p_{k}) + … + (p_{k}^{l_{k}} − p_{k}^{l_{k}−1})) = p_{1}^{l_{1}} … p_{k}^{l_{k}} = n.

Číslo n ∈ ℕ sa nazýva perfektné, ak σ(n) = 2n, t.j. súčet vlastných deliteľov čísla n je rovný n. Perfektné čísla sú napríklad 6=1+2+3 (σ(6) = 12), 28 (σ(28) = 56), 496, 8 128 . Prvá časť nasledujúcej vety bola známa už Euklidovi.

Veta 1.7.7. Ak 2^{n} −1 je prvočíslo, tak a = 2^{n−1}(2^{n} −1) je perfektné a každé párne perfektné číslo má tento tvar.

Dôkaz. Ak 2^{n} − 1 je prvočíslo a a = 2^{n−1}(2^{n} − 1). Potom

σ(a) = σ(2^{n−1}(2^{n} − 1)) = \frac{2^{n} − 1}{2 − 1}(2^{n} − 1 + 1) = 2^{n}(2^{n} − 1) = 2a.

Nech teraz a je párne perfektné číslo. Potom a = m.2^{n−1}, n ≥ 2, m > 0, m je nepárne. Pretože a je perfektné, platí

m.2^{n} = 2a = σ(a) = σ(m.2^{n−1}) = σ(m)σ(2^{n−1}) = σ(m)(2^{n} − 1).

Preto σ(m) = \frac{m.2^{n}}{2^{n}−1} - je to prirodzené číslo, (2^{n}, 2^{n} − 1) = 1, a preto 2^{n} − 1 | m. A preto aj \frac{m}{2^{n}−1} | m. Naviac

σ(m) = \frac{m.2^{n}}{2^{n} − 1} = \frac{m(2^{n} − 1) + m}{2^{n} − 1} = m + \frac{m}{2^{n} − 1}.

Teda m má len 2 kladných deliteľov, a preto m je prvočíslo. Potom \frac{m}{2^{n}−1} = 1, a teda m = 2^{n}−1 je prvočíslo a a = 2^{n−1}(2^{n} − 1).

Pretože nie je známe, či Mersennových prvočísel je nekonečne veľa, nie je známe ani to, či párnych perfektných čísel je nekonečne veľa. V súčasnosti nie je známe ani jedno nepárne perfektné číslo. Je dokázané, že ak existuje, tak má aspoň 8 prvočíselných deliteľov a musí byť väčšie ako 10^{80} (Cohen). V r. 1977 bol avizovaný výsledok, že také číslo musí byť väčšie ako 10^{200} ale dôkaz nebol publikovaný. Naznačuje to však skutočnosť, že asi neexistuje nepárne perfektné číslo.

Cvičenia

1. Vypočítajte φ(144), φ(1000).

2. Vypočítajte σ(144), σ(1000).

3. Určte τ(2p^{3}) a σ(2p^{3}), ak p je nepárne prvočíslo.

1.8 Doplnky. Lagrangeova a Wilsonova veta.

Nech p je prvočíslo a a.x ≡ b (mod p) je lineárna kongruencia. Ak (a, p) = 1, tak daná kongruencia má práve jedno riešenie. Ak teda a.x ≡ b (mod p) má viac ako jedno riešenie, tak (a, p) ≠ 1 a teda (a, p) = p. Potom, keďže má riešenie, platí p | b a pretože (a, p) = p, platí tiež p | a. Okrem lineárnych kongruencií s jednou neznámou možno uvažovať o kongruenciách vyššieho stupňa,

f(x) ≡ 0 (mod n), kde f(x) = a_{n}x^{n} + … + a_{1}x + a_{0}

a a_{0}, a_{1} … a_{n} ∈ ℤ s neznámou x. Pre takéto kongruencie podľa prvočíselného modulu platí analógia horeuvedeného výsledku pre lineárne kongruencie.

Veta 1.8.1 (Lagrangeova). Nech f(x) = a_{n}x^{n} + … + a_{1}x + a_{0} je polynóm s celočíselnými koeficientami, a_{n} ≠ 0 a p je prvočíslo. Potom ak kongruencia

f(x) ≡ 0 (mod p)

má viac ako n riešení, tak pre každé i = 1, …, n

p | a_{i}.

Dôkaz. Pripomeňme, že riešením kongruencie f(x) ≡ 0 (mod p) je zvyšková trieda [c]_{p}, pre ktorú platí, že f(c) ≡ 0 (mod p). Vetu dokážeme indukciou vzhľadom na stupeň n polynómu f(x).

Pre n = 1 máme kongruenciu

a_{1}x + a_{0} ≡ 0 (mod p).

Nech [c_{0}]_{p}, [c_{1}]_{p} sú dve rôzne riešenia tejto kongruencie. Potom c_{0} ≢ c_{1} (mod p) a a_{1}c_{0} +a_{0} ≡ 0 (mod p), a_{1}c_{1} + a_{0} ≡ 0 (mod p). Potom a_{1}c_{0} + a_{0} ≡ a_{1}c_{1} + a_{0} (mod p), a preto

a_{1}c_{0} ≡ a_{1}c_{1} (mod p).

Ak by platilo (a_{1}, p) = 1, tak dostaneme c_{0} ≡ c_{1} (mod p), čo je v spore s predpokladom. Preto platí (a_{1}, p) ≠ 1 a teda p | a_{1}. Potom ale a_{1} ≡ 0 (mod p), a preto a_{1}c_{0} ≡ 0 (mod p). Potom a_{1}c_{0} + a_{0} ≡ a_{0} (mod p) a súčasne a_{1}c_{0} + a_{0} ≡ 0 (mod p). Teda a_{0} ≡ 0 (mod p), t.j. p | a_{0}.

Nech teraz tvrdenie platí pre n ≥ 1. Dokážeme, že potom platí aj pre n + 1. Nech

f(x) = a_{n+1} x^{n+1} + … + a_{1}x + a_{0}

a kongruencia

a_{n+1} x^{n+1} + … + a_{1}x + a_{0} ≡ 0 (mod p)

má n + 2 rôznych riešení [c_{0}]_{p}, [c_{1}]_{p}, …, [c_{n+1} ]_{p}. Teda pre každé i = 0, …, n + 1

f(c_{i}) ≡ 0 (mod p).

Vydelíme polynóm f(x) polynómom x−c_{0} (so zvyškom) a dostaneme f(x) = (x−c_{0}).g(x)+r, kde g(x) = b_{n}x^{n} + … + b_{0}, r ∈ ℤ. Zrejme platí b_{n} = a_{n+1} ≠ 0 a r = f(c_{0}). (f(c_{0}) = (c_{0} − c_{0})g(c_{0}) + r = 0g(c_{0}) + r = r) Teda g(x) je polynóm n-tého stupňa.

Nech i je ľubovoľné číslo 1 ≤ i ≤ n + 1. Potom f(c_{i}) = (c_{i} − c_{0})g(c_{i}) + f(c_{0}) ≡ 0 (mod p). Pretože f(c_{0}) ≡ 0 (mod p), dostávame (c_{i} − c_{0})g(c_{i}) ≡ 0 (mod p) a teda p | (c_{i} − c_{0})g(c_{i}). Pretože [c_{i}]_{p} ≠ [c_{0}]_{p} platí c_{i} ≢ c_{0} (mod p) a teda p ∤ c_{i} − c_{0}. Pretože p je prvočíslo, dostávame p | g(c_{i}) a teda

g(c_{i}) ≡ 0 (mod p).

Teda kongruencia b_{n}x^{n} + … + b_{0} ≡ 0 (mod p) má n + 1 rôznych riešení [c_{1}]_{p}, …, [c_{n+1} ]_{p} a podľa indukčného predpokladu potom p | b_{i} pre i = 0, 1, …, n.

Z platnosti

a_{n+1} x^{n+1} + a_{n}x^{n} + … + a_{1}x + a_{0} = (x − c_{0})(b_{n}x^{n} + b_{n−1}x^{n−1} + … + b_{1}x + b_{0}) + f(c_{0}),

porovnaním koeficientov polynómov, dostávame: a_{n+1} = b_{n}, a_{n} = b_{n−1}−b_{n}c_{0}, a_{n−1} = b_{n−2}− b_{n−1}c_{0}, …, a_{2} = b_{1}−b_{2}c_{0}, a_{1} = b_{0}−b_{1}c_{0}, a_{0} = f(c_{0})−b_{0}c_{0}. Pretože p | b_{n}, b_{n−1}, …, b_{0}, f(c_{0}), je zrejmé, že potom b | a_{n+1} , a_{n} … a_{1}, a_{0}.

Ako dôsledok Lagrangeovej vety dostávame vetu Wilsonovu,^{4} ktorú však ako prvý dokázal Lagrange.

Veta 1.8.2 (Wilsonova). Číslo p > 1 je prvočíslo vtedy a len vtedy, keď

(p − 1)! ≡ −1 (mod p).

4V [1] možno nájsť dôkaz Wilsonovej vety použitím Vandermondovho determinantu.

Dôkaz. ⇒ Pre p = 2 máme 1! = 1 ≡ −1 (mod 2) a teda výrok platí. Nech p > 2. Polynóm

f(x) = (x − 1)(x − 2) … (x − (p − 1)) − (x^{p−1} − 1)

má celočíselné koeficienty a stupeň f(x) je aspoň jedna a je menší alebo rovný ako p − 2. Pre každé k ∈ {1, …, p − 1} platí

f(k) = (k − 1) … \underbrace{(k − k)}_{0}… (k − (p − 1)) − (k^{p−1} − 1) = −k^{p−1} + 1.

Pretože p ∤ k, platí (k, p) = 1 a podľa Eulerovej vety k^{p−1} ≡ 1 (mod p). Potom ale

f(k) = −k^{p−1} + 1 ≡ 0 (mod p).

Teda zvyškové triedy [1]_{p}, [2]_{p}, …, [p − 1]_{p} sú navzájom rôzne riešenia kongruencie f(x) ≡ 0 (mod p), a preto p delí všetky koeficienty f(x). Absolútny koeficient f(x) je číslo (p−1)!+1, a preto p | (p − 1)! + 1. Teda

(p − 1)! ≡ −1 (mod p).

⇐ Nech by p bolo zložené. Potom p = m.n, 1 < m, n < p. Teda p | m.n | (p−1)!, pretože m aj n sa vyskytnú medzi činiteľmi vystupujúcimi v (p−1)!. Dostali sme (p−1)! ≡ 0 (mod p) a súčasne (p − 1)! ≡ −1 (mod p), čo je spor.

Kapitola 2

g-adické rozvoje reálnych čísel. Kritéria iracionálnosti.

V tejto kapitole sa budeme zaoberať reálnymi číslami. Najprv pripomeňme pojem reálneho čísla a pojem celá časť reálneho čísla.

Reálne číslo a sa nazýva racionálne, ak existuje z ∈ ℤ a n ∈ ℕ tak, že a = \frac{z}{n} (ekvivalentne: existuje n ∈ ℕ tak, že a.n ∈ ℤ).

Celé číslo z sa nazýva celá časť reálneho čísla a, ak platí: z ≤ a < z + 1. Označenie: [a]. Teda [a] ∈ ℤ a [a] ≤ a < [a] + 1.

Je zrejmé, že ak a ≥ 0, tak [a] ∈ ℕ_{0}.

Pripomeňme, že ℝ označuje množinu všetkých reálnych čísel, ℝ^{+} = {a ∈ ℝ : a > 0} a ℝ_{0}^{+} = ℝ^{+} ∪ {0}. ℚ označuje množinu všetkých racionálnych čísel, ℚ^{+} = {r ∈ ℚ; r > 0}, ℚ_{0}^{+} = ℚ^{+} ∪ {0}.

2.1 g-adický rozvoj

Veta 2.1.1. Nech g ∈ ℕ, g ≥ 2. Potom každé reálne číslo r ∈ ℝ_{0}^{+} možno jednoznačne

vyjadriť v tvare r = c_{0} + \frac{c_{1}}{g} + \frac{c_{2}}{g^{2}} + … + \frac{c_{k}}{g^{k}} + … = c_{0} + ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}}, kde c_{0} ∈ ℕ_{0}, pre každé k ∈ ℕ

c_{k} ∈ {0, 1, …, g − 1} a pre nekonečne veľa k ∈ ℕ platí c_{k} < g − 1.

Dôkaz. Existencia. Položme c_{0} = [r], r_{1} = r − c_{0}. Zrejme 0 ≤ r_{1} < 1 a r = c_{0} + r_{1}. Ďalej, c_{1} = [g.r_{1}], r_{2} = g.r_{1} − c_{1}. Platí 0 ≤ r_{2} < 1, gr_{1} = c_{1} + r_{2}. Z 0 ≤ gr_{1} < g vyplýva 0 ≤ [gr_{1}] < g, t.j. 0 ≤ c_{1} < g. c_{2} = [g.r_{2}], r_{3} = gr_{2} − c_{2}. Platí 0 ≤ r_{3} < 1, gr_{2} = c_{2} + r_{3}, 0 ≤ [gr_{2}] ≤ gr_{2} < g, t.j. 0 ≤ c_{2} < g. Takto možno pokračovať matematickou indukciou, t.j. predpokladajme, že máme definované c_{n}, 0 ≤ c_{n} < g, r_{n+1} , 0 ≤ r_{n+1} < 1. Potom definujeme

c_{n+1} = [g.r_{n+1} ], r_{n+2} = gr_{n+1} − c_{n+1} ,

pričom platí 0 ≤ r_{n+2} < 1, g.r_{n+1} = c_{n+1} +r_{n+2} a 0 ≤ [gr_{n+1} ] ≤ gr_{n+1} < g, t.j. 0 ≤ c_{n+1} < g. Tým je pre každé k ∈ ℕ definované c_{k} ∈ {0, 1, …, g − 1} a r_{k} ∈ [0, 1), pričom platí gr_{k+1} = c_{k+1} + r_{k+2} a r = c_{0} + r_{1}. Teda

r = c_{0} + r_{1} = c_{0} + \frac{gr_{1}}{g} = c_{0} + \frac{c_{1} + r_{2}}{g} = c_{0} + \frac{c_{1}}{g} + \frac{r_{2}}{g} =

= c_{0} + \frac{c_{1}}{g} + \frac{gr_{2}}{g^{2}} = c_{0} + \frac{c_{1}}{g} + \frac{c_{2}}{g^{2}} + \frac{r_{3}}{g^{2}} = … = c_{0} + \frac{c_{1}}{g} + \frac{c_{2}}{g^{2}} + … + \frac{c_{n}}{g^{n}} + \frac{r_{n+1}}{g^{n}}

Označme s_{n} = c_{0} + \frac{c_{1}}{g} + \frac{c_{2}}{g^{2}} + … + \frac{c_{n}}{g^{n}}. Potom 0 ≤ r − s_{n} = \frac{r_{n+1}}{g^{n}} < \frac{1}{g^{n}}. Pretože lim_{n→∞} \frac{1}{g^{n}} = 0,

platí lim_{n→∞} s_{n} = r. Pritom lim_{n→∞} s_{n} = c_{0} + ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}} a teda

r = c_{0} + \frac{c_{1}}{g} + \frac{c_{2}}{g^{2}} + … + \frac{c_{n}}{g^{n}} + … = c_{0} + ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}} .

Nech K = {k ∈ ℕ; c_{k} < g − 1} je konečná. Potom K má najväčší prvok k_{0}. Teda pre každé n ≥ k_{0} + 1 je c_{n} = g − 1. Z toho potom dostávame:

0 ≤ \frac{r_{k_{0} +1}}{g^{k_{0}}} = r − (c_{0} + \frac{c_{1}}{g} + … + \frac{c_{k_{0}}}{g^{k_{0}}} ) = ∑_{n=k_{0} +1}^{∞} \frac{c_{n}}{g^{n}} =

= ∑_{n=k_{0} +1}^{∞} \frac{g − 1}{g^{n}} = \frac{g − 1}{g^{k_{0} +1}} + \frac{g − 1}{g^{k_{0} +2}} + … + \frac{g − 1}{g^{k_{0} +m}} + … = \frac{g − 1}{g^{k_{0}}} (\frac{1}{g} + \frac{1}{g^{2}} + … + \frac{1}{g^{m}} + …) =

= \frac{g − 1}{g^{k_{0}}} \frac{\frac{1}{g}}{1 − \frac{1}{g}} = \frac{g − 1}{g^{k_{0}}} = \frac{g − 1}{g^{k_{0}}} · \frac{1}{g − 1} = \frac{1}{g^{k_{0}}}

Teda \frac{r_{k_{0} +1}}{g^{k_{0}}} = \frac{1}{g^{k_{0}}} , a preto r_{k_{0} +1} = 1, čo je spor (pre každé n ∈ ℕ je totiž r_{n} < 1). Teda K je nekonečná množina.

Jednoznačnosť. Nech r = c_{0} + ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}} = c′_{0} + ∑_{k=1}^{∞} \frac{c′_{k}}{g^{k}}, c_{0}, c′_{0} ∈ ℕ_{0}, pre každé k ∈ ℕ

c_{k}, c′_{k} ∈ {0, 1, …, g − 1} a K = {k ∈ ℕ; c_{k} < g − 1} aj K′ = {k ∈ ℕ; c′_{k} < g − 1} sú nekonečné.

Nech l ∈ K. Potom c_{l} < g − 1 a

\frac{c_{1}}{g} + … + \frac{c_{l}}{g^{l}} < \frac{g − 1}{g} + … + \frac{g − 1}{g^{l}}.

Platí tiež

∑_{k=l+1}^{∞} \frac{c_{k}}{g^{k}} ≤ ∑_{k=l+1}^{∞} \frac{g − 1}{g^{k}},

lebo pre každé k > l c_{k} ≤ g − 1.

Potom ale

0 ≤ ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}} < ∑_{k=1}^{∞} \frac{g − 1}{g^{k}} = \frac{g − 1}{g} + … + \frac{g − 1}{g^{n}} + … =

= (g − 1) (\frac{1}{g} + … + \frac{1}{g^{n}} + …) = (g − 1)\frac{1}{g − 1} = 1.

Teda c_{0} ≤ c_{0} + ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}} < c_{0} + 1 a preto c_{0} = [r]. Podobne sa ukáže, že c′_{0} = [r] a teda c_{0} = c′_{0}.

Nech {k ∈ ℕ; c_{k} ≠ c′_{k}} ≠ ∅ a m je najmenší prvok tejto množiny, t.j. ak l < m, tak c_{l} = c′_{l}. Potom c_{0} + \frac{c_{1}}{g} + … + \frac{c_{l}}{g^{l}} = c′_{0} + \frac{c′_{1}}{g} + … + \frac{c′_{l}}{g^{l}} a preto aj

∑_{k=m}^{∞} \frac{c_{k}}{g^{k}} = ∑_{k=m}^{∞} \frac{c′_{k}}{g^{k}} / · \frac{1}{g^{m}}

s = c_{m} + ∑_{k=m+1}^{∞} \frac{c_{k}}{g^{k−m}} = c′_{m} + ∑_{k=m+1}^{∞} \frac{c′_{k}}{g^{k−m}} .

Pretože množiny K, K′ sú nekonečné, existujú l, l′ ≥ m+1 tak, že c_{l} < g −1, resp. c′_{l} < g −1. Potom, podobne ako v predošlej časti dôkazu, ukážeme, že

∑_{k=m+1}^{∞} \frac{c_{k}}{g^{k−m}} = \frac{c_{m+1}}{g} + \frac{c_{m+1}}{g^{2}} + … < \frac{g − 1}{g} + \frac{g − 1}{g^{2}} + … = 1

a teda c_{m} = [s].

Podobne, ∑_{k=m+1}^{∞} \frac{c′_{k}}{g^{k−m}} < 1 a preto c′_{m} = [s]. Teda c_{m} = c′_{m} … spor.

Preto {k ∈ ℕ, c_{k} ≠ c′_{k}} = ∅, t.j. pre každé k ∈ ℕ c_{k} = c′_{k}.

Nech r ∈ ℝ_{0}^{+} , g ∈ ℕ, g ≥ 2. Vyjadrenie r = c_{0}+ ∑_{k=1}^{∞} \frac{c_{k}}{g^{k}} z predošlej vety sa nazýva g-adický

rozvoj čísla r a zapisuje sa aj v tvare r = (c_{0}, c_{1}c_{2} … c_{n} …)_{g}.

Príklad. Nájdite g-adický rozvoj čísla \frac{19}{3} pre g = 5.

\frac{19}{3} = 6 + \frac{1}{3},  c_{0} = 6,  r_{1} = \frac{1}{3}
5r_{1} = \frac{5}{3},  c_{1} = [\frac{5}{3}] = 1,  r_{2} = 5r_{1} − c_{1} = \frac{2}{3}
5r_{2} = \frac{10}{3},  c_{2} = [\frac{10}{3}] = 3,  r_{3} = 5r_{2} − c_{2} = \frac{1}{3}
5r_{3} = \frac{5}{3},  c_{3} = [\frac{5}{3}] = 1,  r_{4} = 5r_{3} − c_{3} = \frac{2}{3}
5r_{4} = \frac{10}{3},  c_{4} = [\frac{10}{3}] = 3,  …

\frac{19}{3} = 6 + \frac{1}{5} + \frac{3}{5^{2}} + \frac{1}{5^{3}} + \frac{3}{5^{4}} + … = (6, 1313\overline{13}…)_{5}.

Poznámka. Ak r < 0, tak −r > 0 a existuje g-adický rozvoj −r = (c_{0}, c_{1}c_{2} … c_{n} …)_{g}. Potom vyjadrenie pre r je r = −(c_{0}, c_{1}c_{2} … c_{n} …)_{g}.

2.2 Kritériá racionálnosti

Definícia 2.2.1. Nech r ∈ ℝ_{0}^{+} , g ∈ ℕ, g ≥ 2. g-adický rozvoj r = (c_{0}, c_{1} … c_{n} …)_{g} čísla r nazývame periodický, ak existuje m ∈ ℕ_{0} a k ∈ ℕ tak, že pre každé l ∈ ℕ, l > m platí c_{k+l} = c_{l}. Nech m, k sú najmenšie také čísla. Potom r = (c_{0}, c_{1} … c_{m}d_{1} … d_{k}d_{1} … d_{k} …)_{g}, pričom postupnosť c_{1}, …, c_{m} sa nazýva predperióda a postupnosť d_{1}, …, d_{k} (základná) perióda gadického rozvoja čísla r.

r = 2, \underbrace{123} 4545_{predperióda}\underbrace{\overline{45}} …_{základná perióda}

Veta 2.2.2. Nech g ∈ ℕ, g ≥ 2. Číslo r ∈ ℝ_{0}^{+} je racionálne vtedy a len vtedy, ak g-adický rozvoj r = (c_{0}, c_{1} … c_{n} …)_{g} čísla r je periodický.

Dôkaz. Ak r = (c_{0}, c_{1} … c_{n}c_{n+1} …)_{g} je g-adický rozvoj r, tak g^{n}.r = g_{0}g^{n} + c_{1}g^{n−1} + … + c_{n} + \frac{c_{n+1}}{g} + \frac{c_{n+2}}{g^{2}} + … a [g^{n}r] = c_{0}g^{n} + … + c_{n}. Teda g^{n}r − [g^{n}r] = \frac{c_{n+1}}{g} + \frac{c_{n+2}}{g^{2}} + … = (0, c_{n+1} c_{n+2} …)_{g}.

⇐ Nech teraz r = (c_{0}, c_{1}, …, c_{m}d_{1}, …, d_{k}d_{1}, …, d_{k} …)_{g} má periodický g-adický rozvoj

s predperiódou c_{1}, …, c_{m} a periódou d_{1}, …, d_{k}.

Potom g^{m}.r − [g^{m}.r] = 0, d_{1} … d_{k}d_{1} … d_{k} …
a g^{m+k} .r − [g^{m+k} .r] = 0, d_{1} … d_{k}d_{1} … d_{k} …
Teda g^{m}r − [g^{m}r] = g^{m+k} r − [g^{m+k} r]. Potom
(g^{m+k} − g^{m})r = [g^{m+k} r] − [g^{m}r] a teda

r = \frac{[g^{m+k} r] − [g^{m}r]}{g^{m+k} − g^{m}}∈ ℚ.

⇒ Nech r ∈ ℚ_{0}^{+} , r = (c_{0}, c_{1}c_{2} … c_{n} …)_{g}. c_{0} = [r] ∈ ℕ_{0} a r − c_{0} = \frac{a}{b} ∈ ℚ ∩ [0, 1),

r − c_{0} = (0, c_{1}c_{2} … c_{n} …)_{g}. Ak a = 0, tak r = (c_{0}, 00 … 0 …)_{g} má periodický rozvoj. Ak a ≠ 0, tak \frac{a}{b} > 0 a a, b možno zvoliť tak, že a > 0 aj b > 0. Stačí dokázať, že g-adický rozvoj \frac{a}{b} je periodický.

\frac{a}{b} = (0, c_{1}c_{2} … c_{n} …)_{g} ∀n ∈ ℕ v_{n} = g^{n} \frac{a}{b} − [g^{n} \frac{a}{b}] = (0, c_{n+1} c_{n+2} …)_{g} a 0 ≤ v_{n} < 1. Preto 0 ≤ v_{n}b < b, pričom

v_{n}.b = g^{n}.a − [g^{n} \frac{a}{b}].b ∈ ℕ_{0}.

Teda v_{n}.b ∈ \{0, 1, …, b − 1\} a potom v_{n} ∈ \{0, \frac{1}{b} , …, \frac{b−1}{b} \} - konečná množina. Teda postupnosť {v_{n}}_{n=1}^{∞} má len konečný počet hodnôt a preto existujú m, n ∈ ℕ, m < n také, že v_{m} = v_{n}. Označme k = n − m. Potom k ∈ ℕ a v_{n} = v_{m+k} . Pritom

v_{m} = (0, c_{m+1} c_{m+2} … c_{m+k} c_{m+k+1} … c_{m+2k} c_{m+2k+1} … c_{m+3k} …)_{g}
v_{m+k} = (0, c_{m+k+1} … c_{m+2k} c_{m+2k+1} … c_{m+3k} …)_{g}

Pretože v_{m} = v_{m+k} a g-adický rozvoj je daný jednoznačne, dostávame: c_{m+1} = c_{m+k+1} , c_{m+2} = c_{m+k+2} , … c_{m+k} = c_{m+2k} , c_{m+k+1} = c_{m+2k+1} , … Teda pre každé l > m platí c_{l} = c_{l+k} a preto g-adický rozvoj čísla \frac{a}{b} je periodický.

Príklad. Vyjadrite číslo r = 2, 21123123123 … v tvare \frac{z}{n}, z ∈ ℤ, n ∈ ℕ. m = 2 (dĺžka predperiódy) k = 3 (dĺžka periódy) r = \frac{[10^{m+k} r]−[10^{m}r]}{10^{m}(10^{k}−1)}

r = \frac{[10^{5} r]−[10^{2} r]}{10^{2} (10^{3} −1)} = \frac{221123−221}{100.999} = \frac{220902}{99900} = \frac{36817}{16650}

Ďalšie kritériá pre racionálnosť (alebo aj iracionálnosť) niektorých reálnych čísel sú

Veta 2.2.3. Nech n, m ∈ ℕ a n ≥ 2. Potom \sqrt[n]{m} je racionálne číslo vtedy a len vtedy, ak existuje k ∈ ℕ, pre ktoré k^{n} = m.

Dôkaz. ⇒ Nech \sqrt[n]{m} je racionálne číslo. Pretože \sqrt[n]{m} > 0, existujú a, b ∈ ℕ tak, že \sqrt[n]{m} = \frac{a}{b} a (a, b) = 1. Potom platí b^{n}.m = a^{n}. Pretože (a, b) = 1, platí aj (a^{n}, b^{n}) = 1. Číslo a^{n} delí b^{n}.m, (a^{n}, b^{n}) = 1 a preto a^{n} | m. Potom m = l.a^{n}. Teda platí b^{n}.l.a^{n} = a^{n}, z čoho dostaneme b^{n}.l = 1. Potom ale b | 1 a preto b = 1. Teda máme m = a^{n}, a ∈ ℕ.

⇐ Zrejmé. \sqrt[n]{m} = \sqrt[n]{k^{n}} = k ∈ ℕ ⊆ Q

Nech log označuje logaritmus pri základe 10. Potom platí

Veta 2.2.4. Pre každé r ∈ ℚ^{+} , logr ∈ ℚ vtedy a len vtedy, keď existuje z ∈ ℤ také, že r = 10^{z}.

Dôkaz. ⇒ Nech r > 1, r = \frac{a}{b}, a, b ∈ ℕ, a > b, (a, b) = 1 a nech log \frac{a}{b} ∈ ℚ. Potom 10^{\frac{c}{d}} = \frac{a}{b} a teda 10^{c} = (\frac{a}{b})^{d}. Po úprave, 10^{c}.b^{d} = a^{d}. Pretože (a, b) = 1, platí aj (b, a^{d}) = 1. Pretože b | a^{d}, máme (b, a^{d}) = b = 1. Teda máme 10^{c} = a^{d}. 10^{c} = 2^{c}5^{c} = a^{d}, t.j. a^{d} = 2^{c}5^{c} je kanonický rozklad a^{d}. Z jednoznačnosti kanonického rozkladu vyplýva, že v kanonickom rozklade čísla a sú práve čísla 2 a 5, t.j. a = 2^{u}.5^{v} je kanonický rozklad a, u, v ∈ ℕ. Potom a^{d} = 2^{ud}.5^{vd} = 2^{c}.5^{c}, z čoho dostávame, že ud = c = vd. Pretože (c, d) = 1 a d | c, platí (c, d) = d = 1. Teda 10^{u} = a = \frac{a}{b} = r.

Nech teraz r < 1. Potom \frac{1}{r} > 1 a platí logr = − log \frac{1}{r}. Ak logr ∈ ℚ, tak aj log \frac{1}{r} ∈ ℚ a preto existuje n ∈ ℕ tak, že \frac{1}{r} = 10^{n}. Potom r = 10^{−n} a −n ∈ ℤ.

Pre r = 1 platí r = 10^{0}.

⇐ Zrejmé. log10^{z} = z ∈ ℚ

Cvičenia

1. Dokážte, že nasledujúce číslo sú iracionálne: a) \sqrt{3} + \sqrt{5}, b) \sqrt{3}(\sqrt{6} − 3), c)\frac{4\sqrt{3}−3}{6} , d)\sqrt{3} − \sqrt{2}, e) \sqrt[3]{3} + \sqrt{2}, f) log2 + log3, g) 10^{\frac{9}{7}} , h) \sqrt{2} + \sqrt{3} + \sqrt{5}.

2. Nech r = \frac{c}{d}, (c, d) = 1, d, c ∈ ℤ, je racionálny koreň rovnice a_{k}x^{k}+a_{k−1}x^{k−1}+… a_{0} = 0, pričom a_{0}, …, a_{k} ∈ ℤ, a_{k} ≠ 0. Dokážte, že potom c | a_{0} a d | a_{k}. Z toho dostaneme, že pre rovnicu x^{k} + a_{k−1}x^{k−1} + … + a_{1}x + a_{0} = 0, a_{i} ∈ ℤ platí: Každý racionálny koreň tejto rovnice je celé číslo.

3. Nájdite 5-adický rozvoj nasledujúcich čísel: \frac{35}{11} , \frac{13}{9} , \frac{1}{24} .

4. Nájdite celé čísla a, b tak, aby a) \frac{a}{b} = 0, 123, b) \frac{a}{b} = 2, 1\overline{25}, a) \frac{a}{b} = 3, \overline{9157}.

5. Nájdite a, b ∈ ℤ tak, aby a) \frac{a}{b} = 2 + \frac{1}{5} + \frac{3}{5^{2}} + \frac{1}{5^{3}} + \frac{3}{5^{4}} + \frac{1}{5^{5}} + \frac{3}{5^{6}} + … = (2, 131313 …)_{5}

b) \frac{p}{q} = 3 + \frac{2}{7} + \frac{3}{7^{2}} + \frac{3}{7^{3}} + \frac{3}{7^{4}} + … = (3, 23333 …)_{7}.

Literatúra

[1] Š. Znám: Teória čísel, Alfa, Bratislava, 1986.

[2] M. Kolibiar a kol.: Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.

[3] T. Šalát a kol.: Algebra a teoretická aritmetika 2, Alfa, Bratislava, 1986.

[4] C. T. Long: Elementary introduction to number theory, 3rd ed., Englewood Cliffs, NJ: Prentice-Hall, 1987.

[5] M. Kolibiar a kol.: Vybrané partie z matematiky (skriptum), UK, Bratislava, 1979.

[6] T. Šalát: Vybrané kapitoly z elementárnej teórie čísel (skriptum), UK, Bratislava, 1979.

[7] T. Hecht, Z. Sklenáriková: Metódy rieše, SPN, Bratislava, 1992.

[8] J. B. Dynkin a kol.: Matematické hlavolamy, Alfa, Bratislava.