Základní pojmy
Řešené příklady
Příklad. Dokažte: n  N : 64|32n+3
+ 40n - 27.
Řešení. Důkaz povedeme matematickou indukcí:
1. n = 1: 32n+3
+ 40n - 27 = 32+3
+ 40 - 27 = 243 + 40 - 27 = 256 = 4  64
2. Nechť 64|32n+3
+ 40n - 27 pro n  {1, 2, . . ., k}.
3. k = n + 1. Pak 32k+3
+ 40k - 27 = 32(n+1)+3
+ 40(n + 1) - 27 =
= 32n+3+2
+ 40n + 40 - 27 = 32
 32n+3
+ 40n - 27 + 40 =
= 9  (32n+3
+ 40n - 27) - 8  (40n - 27) + 40 =
= 9  (32n+3
+ 40n - 27) - 64  5n + 256 = 9  (32n+3
+ 40n - 27) + 64(4 - 5n)
Příklad. Nechť (u, v) = 1. Dokažte, že (u + v, u - v) je rovno buď 1 nebo 2.
Řešení. Jak u, tak v může být buď sudé, nebo liché.
1. u - sudé, v - sudé
Není splněn předpoklad (u, v) = 1.
2. u - liché, v - liché, tj. u = 2k + 1, v = 2l + 1, k, l  Z
Předpokládejme, že existuje prvočíslo p = 2 : p|(u + v)  p|(u - v)., tj. platí
u + v = pm, m  Z
u - v = pn, n  Z
Ze součtu těchto dvou rovnic plyne, že p|u, z jejich rozdílu plyne p|v, což je spor se
zadáním.
Tedy platí: (u + v, u - v) = (2k + 1 + 2l + 1, 2k + 1 - 2l - 1) = 2.
3. u - liché, v - sudé
Součet i rozdíl čísel u, v v tomto případě je vždy liché číslo, jejich společným dělitelem
tedy nemůže být číslo 2. Pokud by čísla u, v byla soudělná a jejich největším
společným dělitelem bylo číslo k, pak by součet i rozdíl byl dělitelný tímto k, a to
by také bylo největším společným dělitelem součtu a rozdílu u, v. Protože k = 1, je
i (u + v, u - v) = k = 1.
1
4. v - liché, u - sudé
Analogicky jako předchozí případ.
Příklad. Pomocí Euklidova algoritmu určete největšího společného dělitele čísel 345
- 1 a
365
- 1.
Řešení.
365
- 1 = (345
- 1)  320
+ (320
- 1)
345
- 1 = (320
- 1)  (325
+ 35
) + (35
- 1)
320
- 1 = (35
- 1)  (315
+ 310
+ 35
+ 1) + 0
(345
- 1, 365
- 1) = 35
- 1
Příklad. Pomocí předchozího příkladu určete Bezoutovu rovnost pro čísla 345
-1 a 365
-1.
Řešení.
35
- 1 = (345
- 1) - (320
- 1)(325
+ 35
) =
= (345
- 1) - [(365
- 1) - (345
- 1)320
](325
+ 35
) =
= (345
- 1) - (325
+ 35
)(365
- 1) + (345
- 1)(345
+ 325
) =
= (345
- 1)(345
+ 325
+ 1) - (365
- 1)(325
+ 35
)
Příklad. Určete, zda jsou daná čísla nesoudělná, popř. po dvou nesoudělná:
1. 6, 10, 15
2. 3, 7, 16
3. 21, 31, 41, 51
Řešení. 1. (6, 10, 15) = 1, (6, 10) = 2, (6, 15) = 3, (10, 15) = 5. Čísla 6, 10, 15 jsou
nesoudělná, ale nejsou po dvou nesoudělná.
2. (3, 7, 16) = 1, (3, 7) = 1, (7, 16) = 1, (3, 16) = 1. Čísla 3, 7, 16 jsou nesoudělná i po
dvou nesoudělná.
3. (21, 31, 41, 51) = 1, (21, 31) = 1, (21, 41) = 1, (21, 51) = 3, (31, 41) = 1, (31, 51) = 1,
(41, 51) = 1. Čísla 21, 31, 41, 51 jsou nesoudělná, ale nejsou po dvou nesoudělná.
Příklad. Nalezněte a  Z, pro která (a - 3)|(a - 3)
2
Řešení.
(a3
- 3) : (a - 3) = a2
+ 3a + 9
- a3
+ 3a2
- 3a2
- 3
- 3a2
+ 9a
9a - 3
- 9a + 27
24
(a - 3)|(a3
- 3)  (a - 3)|(a - 3)(a2
+ 3a + 9)  (a - 3)|24  k  Z : 24 = k  (x - 3)
dělitelé čísla 24: {1, 2, 3, 4, 6, 8, 12, 24}
a  {4, 5, 6, 7, 9, 11, 15, 27, 2, 1, 0, -1, -3, -5, -9, -21}
Příklad. Nalezněte největího společného dělitele (319, 754) = d a určete Bezoutovu rovnost.
Řešení.
754 = 319  2 + 116
319 = 116  2 + 87
116 = 87  1 + 29
87 = 29  3 + 0
(319, 754) = 29
29 = 116 - 87  1 =
= 116 - (319 - 116  2) =
= (754 - 319  2) - (319 - (754 - 319  2)  2) =
= 754 - 319  2 - 319 + 754  2 - 319  4 =
= 754  3 + 319  (-7)
3