1 Základné pojmy

5. Najprv dokážeme, že

(a, b) = 1, (a, c) = 1 ⇒ (a, bc) = 1  (1)

Existujú x, y, z, w tak, že ax + by = 1, az + cw = 1. Potom abz + bcw = b a ax + by = ax + (abz + bcw)y = ax + abyz + bcwy = a(x + byz) + bc.wy = 1. Potom (a, bc) = 1 podľa cvičenia 2.

Ďalej dokážeme

(a, b_{j}) = 1 pre j = 1, …, m ⇒ (a, b_{1} … b_{m}) = 1  (2)

indukciou vzhľadom na m. Pre m = 1 to je vlastne (1). Nech (2) platí pre m, ukážeme, že platí pre m + 1. Ak (a, b_{j}) = 1 pre j = 1, …, m + 1, tak (a, b_{1} … b_{m}) = 1 (indukčný predpoklad) a súčasne (a, b_{m+1} ) = 1. Podľa (1) potom (a, b_{1} … b_{m}b_{m+1} ) = 1.

Zostáva dokázať

(a_{i}, b_{j}) = 1 pre i = 1, …, n, j = 1, …, m ⇒ (a_{1} … a_{n}, b_{1} … b_{m}) = 1.  (3)

Môžeme opäť použiť indukciu vzhľadom na n alebo jednoducho vymeniť úlohy a_{i} a b_{j} v (2). (Pomocou (2) dostaneme najprv, že (b_{1} … b_{m}, a_{i}) = 1 pre všetky prípustné i a z toho vyplýva, že (b_{1} … b_{m}, a_{1} … a_{n}) = 1.)

7. Ak a ≠ 0, b ≠ 0, tak (a, b) existuje. Označme d := (a, b).

⇒ d | a, d | b ⇒ d | ax + by = c

⇐ Nech d | c. Potom c = c′d. Keďže d = (a, b), existujú u, v ∈ ℤ tak, že d = au + bv. Potom c = c′d = ac′u + bc′v, čiže x = c′u, y = c′v je riešenie rovnice ax + by = d.

Ešte popíšeme ako vyzerá množina riešení rovnice

ax + by = c  (4)

Nech x_{0}, y_{0} je nejaké riešenie tejto rovnice a x, y je ľubovoľné iné jej riešenie . Potom a(x − x_{0}) + b(y − y_{0}) = ax + by − (ax_{0} + by_{0}) = 0 a a(x − x_{0}) = −b(y − y_{0}). Vydelením tejto rovnice číslom d dostaneme

\frac{a}{d}(x − x_{0}) = −\frac{b}{d}(y − y_{0}).

(\frac{a}{d}, \frac{b}{d}) = 1 (inak by mali väčšieho spoločného deliteľa). Potom \frac{a}{d} | y − y_{0} a \frac{b}{d} | x − x_{0} (veta z prednášky), t.j. x − x_{0} = t.\frac{b}{d}, y − y_{0} = s.\frac{a}{d}. Dostaneme teda, že každé riešenie možno vyjadriť ako

x = x_{0} + \frac{b}{d}t y = y_{0} − \frac{a}{d}t,

kde parametre t, u ∈ ℤ. (Ľahko sa overí, že je to skutočne riešenie.)

8. Ak mám v niektorej nádobe x litrov a x ≤ 13, tak viem odmerať aj x+4 litrov. (x dám do 13litrovej nádoby, naplním 17l nádobu. Koľko sa zmestí prelejem do 13l nádoby a v 17l mi zostane x + 4 litrov.)

Ak mám x litrov a x ≥ 13, tak viem dostať x − 13. (Prelejem, čo sa dá, do 13l nádoby, a dám pritom pozor aby som neporozlieval.)

Ľahko vyrátame, že 15 = 7.4 − 13. Použitím spomínaných dvoch postupov teda budem vedieť dostať aj 15l.

Treba dať pozor, aby som sa nedostal do záporných čísel alebo nepresiahol obsah nádob. Prípustný postup je napríklad odmerať postupne 4, 8, 12, 16 litrov (1.spôsob), potom 16-13=3 litre (2) a ďalej 7, 11, 15 litrov. (Netvrdím, že sa to nedá jednoduchšie, však skúste;-)

10. Označme: A = všetky prirodzené čísla menšie ako 10^{6}. |A| = 999 999, A_{2} = tie z nich, ktoré sú deliteľné 2, |A_{2}| = ⌊\frac{999 999}{2} ⌋ = 499 999 A_{3} = tie z nich, ktoré sú deliteľné 3, |A_{3}| = 333 333 A_{2} ∩ A_{3} obsahuje práve tie čísla, ktoré sú deliteľné 6, teda |A_{2} ∩ A_{3}| = 166 666. Potom |A_{2} ∪ A_{3}| = |A_{2}| + |A_{3}| − |A_{2} ∩ A_{3}| = 499 999 + 333 333 − 166 666 = 566 666 Toto je počet čísel súdeliteľných s číslom 6, nesúdeliteľných je teda 999 999 − 566 666 = 333 333.

Prípad b) je podobný, len treba skúmať deliteľnosť 2, 3, a 5 a použiť |A_{2} ∪ A_{3} ∪ A_{5}| = |A_{2}| + |A_{3}| + |A_{5}| − |A_{2} ∩ A_{3}| − |A_{2} ∩ A_{5}| − |A_{3} ∩ A_{5}| + |A_{2} ∩ A_{3} ∩ A_{5}|.

15. Rozoberme 3 možné prípady:

Ak a = 3k, tak 3 | a. Ak a = 3k + 1, tak a + 2 = 3k + 3 = 3(k + 1), čiže 3 | a + 2. Ak a = 3k + 2, tak a + 1 = 3k + 3 = 3(k + 1) a 3 | a + 1. (Ak a = 3k + 2, tak a + 4 = 3k + 6 = 3(k + 2) a 3 | a + 4.)

19. a)

(2n + 1) = 1.(2n − 1) + 2  ⇒  2 = (2n + 1) − (2n − 1)
(2n + 1) = n.2 + 2  ⇒  1 = 2n + 1 − 2n = 2n + 1 − [(2n + 1) − (2n − 1)]n =
= (2n + 1)(1 − n) + (2n − 1)n

Podľa cvičenia 2 potom 1 = (2n + 1, 2n − 1).

b) n^{2} − 1 = (n − 1)(n + 1) a n^{2} + n = n(n + 1). Teda n + 1 je spoločným deliteľom týchto čísel.

Súčasne platí n^{2} + n − n^{2} − 1 = n(n + 1) − (n − 1)(n + 1) = n + 1, preto každý ich spoločný deliteľ delí aj n + 1 a n + 1 = (n^{2} + n, n^{2} − 1).

c) n^{3} − 1 = (n − 1)(n^{2} + n + 1), n^{2} − 1 = (n − 1)(n + 1) a n^{2} + n + 1 − n(n + 1) = 1, z čoho dostaneme (n^{2} + n + 1, n + 1) = 1, a (n^{3} − 1, n^{2} − 1) = n − 1.

d) Pomocou delenia so zvyškom dostaneme: (n^{3} + 2) = (n^{2} − n + 1)(n + 1) + 1 a (n^{3} + 2, n + 1) = (n + 1, 1) = 1.

2 Prvočísla

4. Sporom. Nech by k nebolo prvočíslo. Potom k = n.l pre nejaké 1 < n, l < k. Z toho, že l | k a k | m dostaneme, že l | m, čo je spor s tým, že k bolo najmenšie takéto číslo.

5. Nepriamo. Prepokladajme, že n je zložené číslo, ukážeme, že aj 2^{n}−1 je zložené číslo. Ak n = k.l, kde 1 < k, l < n, tak 2^{n}−1 = 2^{k.l}−1 = (2^{k})^{l}−1 = (2^{k}−1)(1+2^{k}+...+2^{k.(l−1)}). (Použili sme vzorec (a^{m} − b^{m}) = (a − b)(a^{m−1} + a^{m−2}b + … + ab^{m−2} + b^{m−1}.) Pretože l > 1, platí 2^{k} − 1 < 2^{k.l} − 1 = 2^{n} − 1. Teda číslo 2^{n} − 1 je zložené.

6. Nepriamo. Nech n ≠ 2^{m}, t.j. n = 2^{m}.(2k + 1) pre nejaké k > 1. Potom 2^{n} + 1 = (2^{2^{m}})^{(2k+1)} + 1. Použitím vzorca a^{2k+1} + 1 = (a + 1)(a^{2k} − a^{2k−1} + … − a + 1) pre a = 2^{2^{m}} dostaneme, že 2^{n} + 1 = (2^{2^{m}} + 1). ((2^{2^{m}})^{2k} − (2^{2^{m}})^{2k−1} + … − 2^{2^{m}} + 1) .

Pretože 2^{2^{m}} + 1 > 1, číslo 2^{n} − 1 je zložené.

8. Označme m = n! − 1. Ak m je prvočíslo, tak niet čo dokazovať. Ak m je zložené číslo, tak je deliteľné nejakým menším číslom. m nemôže byť deliteľné žiadnym z čísel 1, …, n, pretože pre k ≤ n platí (m, k) = (n! − 1, k) = 1. [1 = n! − (n! − 1) = 1 … (k−1)(k+1) … n.k−m. Teda 1 = uk+vm, pre celé čísla u = 1 … (k−1)(k+1) … n, v = −1, z čoho už vyplýva (m, k) = 1.] Preto je m deliteľné nejakým číslom medzi n a n! − 1 a najmenšie takéto číslo je prvočíslo. (cvičenie 4)

10. Označme d = p_{1}^{u_{1}} … p_{k}^{u_{k}}. Pretože u_{i} ≤ t_{i}, u_{i} ≤ s_{i} pre všetky prípustné i, d | a aj d | b. Teda d je spoločný deliteľ a aj b.

Ak d′ | a, d′ | b a d′ > 0, tak v kanonickom rozklade čísla d′ sa nemôžu vyskytovať iné prvočísla, než p_{1}, …, p_{k}. Teda d′ = p_{1}^{r_{1}} … p_{k}^{r_{k}}. d′ | a, preto r_{i} ≤ t_{i}. Podobne z d′ | a vyplýva r_{i} ≤ s_{i}. Celkove teda dostávame r_{i} ≤ min{s_{i}, t_{i}} = u_{i} a d′ | d, d′ < d. Teda d je najväčší spoločný deliteľ čísel a a b.

Dokázali sme, že (a, b) = p_{1}^{u_{1}} … p_{k}^{u_{k}}. Potom [a, b] = \frac{a.b}{(a,b)} = p_{1}^{s_{1} +t_{1} −u_{1}} … p_{k}^{s_{k}+t_{k}−u_{k}} = p_{1}^{v_{1}} … p_{k}^{v_{k}}.

12. 72 = 2^{3}.3^{2} má deliteľe 2^{0}.3^{0} = 1, 2^{0}.3^{1} = 3, 2^{0}.3^{2} = 9, 2^{1}.3^{0} = 2, 2^{1}.3^{1} = 6, 2^{1}.3^{2} = 18, 2^{2}.3^{0} = 4, 2^{2}.3^{1} = 12, 2^{2}.3^{2} = 36, 2^{3}.3^{0} = 8, 2^{3}.3^{1} = 24, 2^{3}.3^{2} = 72.

Delitele 11^{5}.7^{2} = {7^{k}.11^{l}; 0 ≤ k ≤ 2, 0 ≤ l ≤ 5}.

14. Ak n nie je deliteľné 5, tak zvyšok n^{4} po delení 5 je 1 (stačí overiť 4 prípady, tiež to vyplýva z Eulerovej vety, ktorú sa naučíme neskôr) a 5 | n^{4} + 4.

15. Ak sa číslo rovná druhej mocnine prirodzeného čísla, tak všetky prvočísla v jeho kanonickom rozklade musia mať párny exponent. Teda a) ani b) nie sú druhé mocniny prirodzených čísel. Pre c) urobíme kanonický rozklad a zistíme, že 1234321 = 1111^{2}.

157996443 nie je druhá mocnina prirodzeného čísla, lebo druhá mocnina prirodzeného čísla môže mať po delení 4 iba zvyšok 0 alebo 1.

18^{∗}. Máme a_{1} = 0, a_{2} = 2, a_{3} = 5. Ak n = 2k pre k ≥ 2, tak a_{n} = k(2k + 1) − 1 = 2k^{2} + k − 1 = (2k − 1)(k + 1) je zložené číslo (2k − 1 ≥ 3, k + 1 ≥ 3). Ak n = 2k + 1 pre k ≥ 2, tak a_{n} = (2k + 1)(k + 1) − 1 = 2k^{2} + 3k = (2k + 3).k je tiež zložené.

19. Sporom. Predpokladajme, že existuje len konečný počet prvočísel takého tvaru. Nech p_{1}, …, p_{k} sú všetky takéto prvočísla. Položme n = 6p_{1} … p_{k} − 1. Potom p_{1} ∤ n, …, p_{k} ∤ n. Čiže v prvočíselnom rozklade n = q_{1} … q_{l} vystupujú len prvočísla so zvyškom 1 po delení 6, a teda aj n = 6m + 1 pre nejaké m - spor.

20. p je nepárne prvočíslo, preto p + 1 je párne a 2 | p + 1. Ešte treba ukázať, že 3 | p + 1. Rozoberme tri možné prípady: p = 3k ⇒ p nie je prvočíslo, p = 3k + 1 ⇒ p + 2 = 3k + 3 = 3(k + 1) ⇒ p + 2 nie je prvočíslo, zostáva teda prípad p = 3k + 2, vtedy p + 1 = 3k + 3 = 3(k + 1) a 3 | p.

3 Číselné sústavy

1. 217: 3 = 72 : 3 = 24 : 3 = 8 : 3 = 2 1  0  0  2
1513: 3 = 504 : 3 = 168 : 3 = 56 : 3 = 18 : 3 = 6 : 3 = 2 1  0  0  2  0  0
2120: 3 = 706 : 3 = 235 : 3 = 78 : 3 = 26 : 3 = 8 : 3 = 2 2  1  1  0  2  2

217 = (22001)_{3}, 1513 = (2002001)_{3}, 2120 = (2220112)_{3}

2. 12892 = (403032)_{5} = (135404)_{6} (10321)_{4} = 1 + 2.4 + 3.16 + 256 = 313

3. Jedna cifra v štvorkovej sústave zodpovedá dvom cifrám v dvojkovej. Jedna cifra v osmičkovej = 3 cifry v dvojkovej. (301)_{4} = (110001)_{2} (257)_{8} = (10101111)_{2} (111100101)_{2} = (13211)_{4} = (745)_{8} (1100101)_{2} = (1211)_{4} = (145)_{8}

5. 9a_{1} + a_{0} = 10a_{0} + a_{1} ⇒ 8a_{1} = 9a_{0} Hľadáme iba celočíselné riešenia medzi číslami 1, …, 8. (Nulu sme vylúčili, lebo zápis čísla v ľubovoľnej číselnej sústave nesmie začínať nulou.) Vidíme, že platí 9 | a_{1}, teda riešenie neexistuje.

4 Kongruencie

1. 213^{174} + 25^{17} ≡ 3^{174} + 5^{17} ≡ (3^{4})^{43} + 5 ≡ 9 + 5 ≡ 4(mod 10)

(Použili sme to, že 3^{4} ≡ 1 (mod 10) a 5^{n} ≡ 5 (mod 10) pre každé n ∈ ℕ.)

b) 9^{99} + (7^{17})^{17} ≡ (9^{2})^{49}.9 + ((7^{4})^{4}.7)^{17} ≡ 1^{49}.9 + 7^{17} ≡ 9 + 7 ≡ 6(mod 10)

c) 127^{37} + 45^{131} + 109^{18} ≡ 7^{37} + 5^{131} + 9^{18} ≡ 7^{9.4+1} + 5 + 9^{2.9} ≡ 7 + 5 + 1 ≡ 3(mod 10)

2. Indukciou sa dá ľahko dokázať, že 2^{3k} ≡ 1 (mod 7), 2^{(3k+1)} ≡ 2 (mod 7), 2^{(3k+2)} ≡ 4 (mod 7). (Zvyšky 2^{n} po delení siedmimi sú 1, 2, 4, 1, 2, 4, …) Teda

a) 7 | 2^{n} − 1 ⇔ 2^{n} ≡ 1 (mod 7) ⇔ n = 3k, k ∈ ℕ.

b) 7 | 2^{n} − 1 ⇔ 2^{n} ≡ 6 (mod 7), toto neplatí pre žiadne n.

3. Budeme dokazovať dve implikácie.

19 | 10a + b ⇒ 19 | 20a + 2b ⇒ 19 | (20a + 2b) − 19a, t.j. 19 | a + 2b 19 | a + 2b ⇒ 10 | 10a + 20b ⇒ 10 | (10a + 20b) − 19b, t.j. 19 | 10a + b. To isté môžeme zapísať pomocou kongruencií: 10a + b ≡ 0 (mod 19) ⇒ 20a + 2b ≡ 0 (mod 19) ⇒ a + 2b ≡ 0 (mod 19) a + 2b ≡ 0 (mod 19) ⇒ 10a + 20b ≡ 0 (mod 19) ⇒ 10a + b ≡ 0 (mod 19)

4. 19 | 539 828 ⇔ 19 | 53 998 ⇔ 19 | 5 415 ⇔ 19 | 551 ⇔ 19 | 57 ⇔ 19 | 19.

Teda 19 | 539 828.

5. x je párne ⇒ x ≡ 4 (mod 2) ⇒ f(x) ≡ f(4) (mod 2). Teda f(x) je nepárne celé číslo, čiže f(x) ≠ 0. Podobne ak x je nepárne, tak x ≡ 5 (mod 2) ⇒ f(x) ≡ f(5) (mod 2). Opäť f(x) je nepárne, f(x) ≠ 0.

8. Ak a ≡ b (mod n), tak n | a − b. Z toho, že m | n a n | a − b dostaneme, že m | a − b, a ≡ b (mod m).

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

1. Všimnime si najprv, že 27.37 = 999. Zrejme platí 1 ≡ 1000 (mod 999), a teda aj n ≡ 1000n (mod 999) pre ľubovoľné n. Z toho dostaneme:

c_{0} + c_{1}.10 + c_{2}.10^{2} ≡ c_{0} + c_{1}.10 + c_{2}.10^{2} (mod 999)
c_{3} + c_{4}.10 + c_{5}.10^{2} ≡ c_{3}.10^{3} + c_{4}.10^{4} + c_{5}.10^{5} (mod 999)
⋮  ⋮
(c_{0} + c_{1}.10 + c_{2}.10^{2}) + (c_{3} + c_{4}.10 + c_{5}.10^{2}) + … ≡ n (mod 999)

Z toho už vyplýva (c_{0} + c_{1}.10 + c_{2}.10^{2}) + (c_{3} + c_{4}.10 + c_{5}.10^{2}) + … ≡ n (mod 27) a (c_{0} + c_{1}.10 + c_{2}.10^{2}) + (c_{3} + c_{4}.10 + c_{5}.10^{2}) + … ≡ n (mod 37). Možno sa na to pozrieť tiež tak, že keď číslo 1000a + b nahradíme číslom a + b, tak ho zmenšíme o 999a, čiže o násobok 999, teda deliteľnosť 999 tým neovplyvníme.

4. Nepriamo: Nech m je zložené, t.j. m = k.l, 1 < k, l < m. Dokážeme, že aj p je zložené. Platí, že p = (10^{k−1} +10^{k−2} +…+10+1)(10^{k} +10^{2k} +…+10^{(l−1)k}), teda p je zložené. Inak:

11 … 1
11 … 100 … 0
⋮  ⋮
11 … 100 … 0 … 00 … 0
11 … 111 … 1 … 11 … 1

Všetky sčitované čísla sú násobkami čísla \overbrace{11 … 1}^{k}, teda p je zložené.

Obrátená veta neplatí, lebo číslo 111 nie je prvočíslo (je deliteľné 3).

6. a) 4 | 100 ⇒ 4 | c_{2}10^{2}+c_{3}10^{3}+…+c_{k}10^{k} = n−(10c_{1}+c_{0}), teda n ≡ 10c_{1}+c_{0} (mod 4). b) 8 | 1000 ⇒ 8 | c_{3}10^{3} + c_{2}10^{2} + c_{3}10^{3} + … + c_{k}10^{k} = n − (100c_{2} + 10c_{1} + c_{0}), teda n ≡ 100c_{2} + 10c_{1} + c_{0} (mod 4).

7. 7 + 8 + 1 + 2 = 18 ⇒ 8 ∤ (7812)_{9} 7 − 8 + 1 − 2 = −2 ⇒ 10 ∤ (7812)_{9}.

6 Eulerova veta

1. a) Z Eulerovej vety alebo z jej dôsledku dostaneme, že:

7 | n alebo 7 | n^{6} − 1 3 | n alebo 3 | n^{2} − 1 2 | n alebo 2 | n − 1 Pritom n^{7} − n = n(n^{6} − 1) = n(n^{3} − 1)(n^{3} + 1) = n(n − 1)(n^{2} + n + 1)(n^{3} + 1), teda 2, 3, 7 | n^{7} − n. Sú to navzájom rôzne prvočísla, preto 2.3.7 = 42 | n^{7} − n.

b) Ak (n, 7) = 1, tak podľa Eulerovej vety n^{6} ≡ 1 (mod 7). Umocnením tejto kongruencie na k-tu dostaneme n^{6k} ≡ 1 (mod 7). c) 2 | n∨2 | n−1, 3 | n∨3 | n^{2}−1, 5 | n∨5 | n^{4}−1, 7 | n∨7 | n^{6}−1, 13 | n∨13 | n^{12} −1. n^{13} − n = n(n^{12} − 1) = n(n^{6} + 1)(n^{6} − 1) = n(n^{3} − 1)(n^{9} + n^{6} + n^{3} + 1) = n(n^{4} − 1)(n^{8} + n^{4} + 1) = n(n^{2} − 1)(n^{10} + n^{8} + n^{6} + n^{4} + n^{2} + 1) Z toho už vyplýva dokazované tvrdenie.

2. Podľa malej Fermatovej vety p | a^{p} −a a p | (a^{q})^{p} −a^{q} = a^{pq} −a^{q}. Odčítaním dostaneme p | a^{pq} − a^{p} − a^{q} + a. Podobne dostaneme, že q | a^{pq} − a^{p} − a^{q} + a, teda celkove pq | a^{pq} − a^{p} − a^{q} + a.

3. Má platiť 2^{m} − 1 = 3^{n}. Ak m ≥ 3, tak 8 | 2^{m} a 2^{m} − 1 ≡ 7 (mod 8). Ľahko zistíme, že zvyšky 3^{n} po delení 8 sú striedavo 1 (pre párne n) a 3 (pre nepárne). Teda 3^{n} je kongruentné s 1 alebo 3, čo znamená, že riešenie s m ≥ 3 neexistuje. Jediné riešenie je teda m = 2, n = 1.

4. Ak (n, 10) = 1, tak podľa Eulerovej vety n | 10^{φ(n)} − 1, čo je číslo, ktorého zápis v desiatkovej sústave pozostáva z φ(n) deviatok.

5. a) φ(11) = 10 (pre každé prvočíslo platí φ(p) = p − 1). Ak 11 ∤ n, tak (11, n) = 1, teda podľa Eulerovej vety n^{10} ≡ 1 (mod 11).

b) φ(13) = 12. Ak 13 ∤ n, tak (13, n) = 1, teda podľa Eulerovej vety n^{12} ≡ 1 (mod 13).

c) φ(25) = 20, preto ak (n, 25) = 1, tak n^{20} ≡ 1 (mod 25). Ak je n súdeliteľné s 25, tak 5 | n, a preto 5^{2} = 25 | n^{2} | n^{20}.

7. a) Chceme nájsť najmenšie n také, že 253^{n} ≡ 1 (mod 257). 257 je prvočíslo, φ(257) = 256. Podľa cvičenia 6 potom n | 256 = 2^{8}. 253 ≡ −4 (mod 257), umocnením na druhú dostaneme 253^{2} ≡ (−4)^{2} ≡ 16 (mod 257), 253^{4} ≡ 256 ≡ −1 (mod 257), 253^{8} ≡ 1 (mod 257). Teda n = 8.

b) 2^{1} ≡ 2 (mod 257), 2^{2} ≡ 4 (mod 257), …, 2^{8} ≡ 256 ≡ −1 (mod 257), … 2^{16} ≡ 1 (mod 257). n = 16.

8. Podľa Malej Fermatovej vety p^{q−1} ≡ 1 (mod q) a q^{p−1} ≡ 1 (mod p), t.j. q | p^{q−1} − 1 a p | q^{p−1}. Keďže p a q sú navzájom rôzne prvočísla, dostaneme z toho, že pq | (p^{q−1} − 1)(q^{p−1} − 1) = p^{q−1}q^{p−1} − p^{q−1} − q^{p−1} + 1, a teda pq | p^{q−1} + q^{p−1} − 1.

Z kongruencie p^{q−1} + q^{p−1} ≡ 1 (mod pq) vyplýva p^{q} ≡ p^{q} + pq^{p−1} ≡ p (mod pq) a q^{p} ≡ p^{q−1}q + q^{p} ≡ q (mod pq). Sčítaním dostaneme p^{q} + q^{p} ≡ p + q (mod pq).

9. Napríklad a = 2, n = 4, φ(n) = 2.

11^{∗}. Označme d najväčší spoločný deliteľ čísel z množiny {n^{13} − n, n ∈ ℤ}. Z cvičenia 1c) vieme, že 2, 3, 5, 7, 13 | n^{13} − n, čiže 2.3.5.7.13 | d.

Priamym výpočtom overíme, že 2^{13} − 2 = 8190 = 2.3^{2}.5.7.13, preto d | 2.3^{2}.5.7.13.

Pre n = 3 dostaneme 3^{13} − 3 ≡ 6 (mod 9), lebo 9 | 3^{13}. To znamená, že 9 ∤ d a d = 2.3.5.7.13 = 2730.

7 Lineárne kongruencie

2. Podľa vety z prednášky má kongruencia ax ≡ b (mod n) riešenie práve vtedy, keď (a, n) = d | b. Ak má riešenie, tak počet riešení je d.

a) (6, 9) = 3 ∤ 1 nemá riešenie,

b) (9, 6) = 3 | 6 má 3 riešenia,

c) (14, 70) = 14 ∤ 21 nemá riešenie.

3. a) 20x ≡ 4 (mod 30), (20, 30) = 10 ∤ 4 ⇒ nemá riešenie.

b) Táto kongruencia je ekvivalentná s kongruenciou 0 ≡ 2 (mod 4), čiže nemá riešenie.

c) (353, 254) = 1, Euklidovým algoritmom zistíme, že

400 = 353 + 47 ⇒ 47 = 400 − 353
353 = 47.7 + 24 ⇒ 24 = 353 − 7.47 = 8.353 − 7.400
47 = 1.24 + 23 ⇒ 23 = 47 − 24 = 17.353 − 15.400
24 = 23 + 1 ⇒ 1 = 24 − 23 = 17.353 − 15.400

353.17 − 1 = 15.400 ⇒ 353.17 ≡ 1 (mod 400) Poslednú rovnosť vynásobíme 254. 17.254 ≡ 318 (mod 400) ⇒ 353.318 ≡ 254 (mod 400) Jediné riešenie je \underline{\underline{x = 318}} .

8 Aritmetické funkcie

144 = 2^{4}.3^{2} φ(144) = 144 (1 − \frac{1}{2})(1 − \frac{1}{3}) = 144 · \frac{1}{2} · \frac{2}{3} = 48 σ(144) = \frac{2^{5} −1}{1} · \frac{3^{3} −1}{3−1} = \frac{31.26}{2} = 31.13 = 403

1000 = 2^{3}.5^{3} φ(1000) = 1000 (1 − \frac{1}{2})(1 − \frac{1}{5}) = 1000 · \frac{1}{2} · \frac{4}{5} = 400 σ(1000) = \frac{2^{4} −1}{1} · \frac{5^{4} −1}{5−1} = \frac{15.624}{4} = 15.156 = 2340

9 g-adické rozvoje

1. a) Sporom. Nech by a = \sqrt{3}+\sqrt{5} bolo racionálne. Potom a−2\sqrt{3} = \sqrt{5}−\sqrt{3} ∉ ℚ (súčet racionálneho a iracionálneho čísla je iracionálne) a a(a−2\sqrt{3}) = (\sqrt{5}+\sqrt{3})(\sqrt{5}−\sqrt{3}) = 5 − 3 = 2. Súčin racionálneho a iracionálneho čísla je však iracionálne, čiže sme dostali spor.

b) \sqrt{3}(\sqrt{6} − 3) = 3(\sqrt{2} − \sqrt{3}). V d) ukážeme, že \sqrt{3} − \sqrt{2} ∉ Q, čiže aj toto číslo je iracionálne.

c) Súčet racionálneho a iracionálneho čísla je iracionálne.

d) Sporom. a = \sqrt{3} − \sqrt{2} ∈ ℚ, \sqrt{3} + \sqrt{2} = a + 2\sqrt{2} ∉ ℚ, a.b = 1 ∈ ℚ, spor.

e) Nech by a = \sqrt[3]{3} + \sqrt{3} ∈ ℚ.

a − \sqrt{2} = \sqrt[3]{3} /^{3}

a^{3} − 3a^{2} \sqrt{2} + 6a − 2\sqrt{2} = 3

a^{3} + 6a − 3 = (3a^{2} + 2)\sqrt{2}

\sqrt{2} = \frac{a^{3} + 6a − 3}{3a^{2} + 2} ∈ ℚ,

čo je spor. (Deliť v poslednej úprave sme mohli vďaka tomu, že 3a^{2} + 2 > 0.)

f) log2 + log3 = log6 ∉ ℚ podľa vety z prednášky.

\frac{35}{11} = 3 + \frac{2}{11}  \frac{13}{9} = 1 + \frac{4}{9}
5 · \frac{2}{11} = \frac{10}{11} = 0 + \frac{10}{11}  5 · \frac{4}{9} = \frac{20}{9} = 2 + \frac{2}{9}
5 · \frac{10}{11} = \frac{50}{11} = 4 + \frac{6}{11}  5 · \frac{2}{9} = \frac{10}{9} = 1 + \frac{1}{9}
5 · \frac{6}{11} = \frac{30}{11} = 2 + \frac{8}{11}  5 · \frac{1}{9} = \frac{5}{9} = 0 + \frac{5}{9}
5 · \frac{8}{11} = \frac{40}{11} = 3 + \frac{7}{11}  5 · \frac{5}{9} = \frac{25}{9} = 2 + \frac{7}{9}
5 · \frac{7}{11} = \frac{35}{11} = 3 + \frac{2}{11}  5 · \frac{7}{9} = \frac{35}{9} = 3 + \frac{8}{9}
\frac{35}{11} = \underline{\underline{(3, \overline{04233})_{5}}}  5 · \frac{8}{9} = \frac{40}{9} = 4 + \frac{4}{9}
\frac{13}{9} = \underline{\underline{(1, \overline{210234})_{5}}}

Zišlo by sa urobiť aj nejakú skúšku správnosti. Jedna z možností je použiť postup z príkladu 5, ale pri dlhých periódach je tento postup veľmi pracný. Mne by sa zdalo jednoduchšie vynásobiť tie výsledok menovateľom (11 = (21)_{5}) v 5-kovej sústave. (Ak prídete na lepší nápad, ako urobiť skúšku dajte mi vedieť.)

a) \begin{matrix}(3, & \overline{04233})_{5} \\ (21)_{5} \\ (3, & \overline{04233})_{5} \\ (111, & \overline{40211})_{5} \\ (114, & \overline{44444}) = (115)_{5} \end{matrix}

x = \frac{(115)_{5}}{(21)_{5}} = \frac{35}{9}

b) a = (1, \overline{210234})_{5} 10a = (20)_{5}a = (2\overline{4, 20468}). Tento zápis ale ešte nie je korektný zápis čísla v 5-kovej sústave, preto ho musíme ešte upraviť: 10a = (2\overline{4, 21023})_{5} 9a = 10a − a = (24, \overline{210234})_{5} − (1, \overline{210234})_{5} = (23)_{5} = 13 a = \frac{13}{9}

c) \frac{1}{24} = \frac{1}{5^{2} −1} = \frac{1}{5^{2}} (\frac{1}{1−5^{−2}} ) = \frac{1}{5^{2}} (1 + \frac{1}{5^{2}} + \frac{1}{5^{4}} + …) = (0, \overline{01})_{5}

5. x = (2, \overline{13})_{5}, 25x = (213, \overline{13})_{5} ⇒ 24x = (211)_{5} = 56, x = \underline{\underline{\frac{7}{3}}}

x = (3, 2\overline{3})_{7}, 2x = (6, 4\overline{6})_{7} = (6, 5)_{7}, 7.2x = (65)_{7} = 47 ⇒ x = \underline{\underline{\frac{47}{14}}}