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

1.1 Základné pojmy a ich vlastnosti 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). 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|. 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. 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). 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. Lema 1.1.6. Nech a, b, c, c′ ∈ ℤ, b ≠ 0 a a = c′b + c. Potom (a, b) = (b, c). Veta 1.1.7 (výpočet najväčšieho spoločené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.

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. 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]. 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|. 1.2 Prvočísla 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). 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. 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ôsledok 1.2.4. Pre každé n ∈ ℕ, n > 1 existuje prvočíslo p také, že p | n. Veta 1.2.5. Množina všetkých prvočísel je nekonečná. 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ô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.

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.

1.3 Číselné sústavy

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} + … 1 + c_{1}g + c_{0}. Toto vyjadrenie je jednoznačné.

1.4 Kongruencie

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). 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) a 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) a (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). 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. 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}. 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. 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. 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}. 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} − . . .. 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}

1.5 Eulerova funkcia a Eulerova veta Definícia 1.5.1 (Eulerova^{1} 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.) Veta 1.5.2 (Eulerova). Nech n ∈ ℕ. Potom pre každé a ∈ ℤ, pre ktoré (a, n) = 1, platí

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ôsledok 1.5.4 (Malá veta Fermatova). Ak p je prvočíslo, tak pre každé a ∈ ℤ platí

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

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}} )

1.6 Lineárne kongruencie s jednou neznámou 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). 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í. 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), Lema 1.7.2. Ak f je multiplikatívna aritmetická funkcia, tak 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. 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)

1Euler 1707-1783

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

Veta 1.7.6. Pre Eulerovu funkciu φ platí:

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

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.

1.8 Doplnky. Lagrangeova a Wilsonova veta.

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}.

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

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

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

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.

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.

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ý.

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.

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