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

1.1 Základné pojmy a ich vlastnosti

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. 1.2 Prvočísla

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, 641 | F_{5}^{2}.]

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

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

1mních Mersenne 1644 2Euler 1930

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é.)

1.3 Číselné sústavy 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 Pojem kongruentnosti mod n, základné vlastnosti

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 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?

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

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

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

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

1.6 Lineárne kongruencie s jednou neznámou

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 φ, τ, σ

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.

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

2.1 g-adický rozvoj

2.2 Kritériá racionálnosti

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.

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