10 ноября.

Кто малого не может, тому и большое невозможно.

М.В. Ломоносов

Листок 5. Алгоритм Евклида.

Определение. Число d называется общим делителем чисел a и b, если a ··· d и b ··· d. Наибольшее из таких чисел называется наибольшим общим делителем a и b и обозначается НОД (a, b) или (a, b).

\underline{Примечание.} Если a = b = 0, то любое число является общим делителем a и b, и НОД (a, b) не определен.

1. Найдите: а) НОД (7923, 327);  б) НОД (1609, 424);  в) НОД (2342, 876).

Определение. Числа a и b называются взаимно простыми, если НОД (a, b) = 1.

2. докажите, что НОД (a, b) = НОД (a ± b, b). 3! Алгоритм Евклида. Пусть a > b > 0, r — остаток от деления a и b.

а) Докажите, что НОД (a, b) = НОД (b, r).

б) Рассмотрим преобразование (a, b) → (b, r). К полученной паре (b, r) можно применить его еще раз, и т.д. Докажите, что этот процесс закончится за конечное число шагов на паре (НОД (a, b), 0). Данный способ нахождения НОД (a, b) называется алгоритмом Евклида.

4. Найдите (a, b), если: а) a ··· b;  б) a, b — простые;  в) |a − b| = 1;  г) a = \frac{c}{(c, d)}, b = \frac{d}{(c, d)}.

5. Три автомата могут выполнять такие преобразования: первый автомат пару чисел (m, n) преобразует в пару (m + n, n), второй — в пару (m − n, n), третий — в пару (n, m). Пусть в начале имеется пара чисел (29, 93). Можно ли при помощи автоматов получить из нее пару а) (8, 13); б) (17, 51)? 6! Используя алгоритм Евклида, докажите, что если НОД (a, b) = d, то:

а) существуют x, y ∈ ℤ такие, что ax + by = d; б) {ax + by : x, y ∈ ℤ} = {kd : k ∈ ℤ}.

7. Докажите, что при (a, b) = 1 среди чисел a, a + b, a + 2b, …, a + (n − 1)b обязательно найдется число, кратное n.

8. Найдите необходимые и достаточные условия того, что уравнение ax + by = c имеет решение в целых числах. (Уравнения такого вида называются диофантовыми уравнениями 1-го порядка.)

9. Решите в целых числах: а) 13x + 8y = 4;  б) 9x − 6y = 12;  в) 15x + 5y = 3.

\underline{Указание.} Используйте предыдущую задачу.

10! Пусть a > b > 0, a = q_{1}b + r_{1} и c = q_{2}b + r_{2}. Пусть уравнение ax + by = c имеет решение (x_{1}, y_{1}).

а) Докажите, что в этом случае уравнение bx + r_{1}y = r_{2} тоже имеет некоторое целочисленное решение (x_{2}, y_{2}), причем x_{1} = y_{2}, y_{1} = x_{2} − q_{1}y_{2} + q_{2}, b > r_{1} ⩾ 0.

б) Предложите и обоснуйте способ нахождения целочисленных решений исходного уравнения.

11. Докажите, что если ab ··· m и a взаимно просто с m, то b ··· m. \underline{Указание.} Используйте задачу 6.

12. Докажите, что если ab ··· p, то a ··· p или b ··· p. 13*! Основная теорема арифметики. Докажите, что любое целое число можно разложить в произведение простых множителей единственным образом (с точность до перестановок множителей). 14*. Пусть f(x) — многочлен с целыми коэффициентами. Докажите, что существует n ∈ ℤ такое, что f(n) является составным.

15. Выпишите разложения на множители для чисел 18, 56, 125, 127, 1001.

16. У числа 91! посчитали сумму цифр, у получившегося числа снова посчитали сумму цифр, и т.д. до тех пор, пока не получили однозначное число. Какое?

Определение. НОК (a_{1}, a_{2}, …, a_{k}) (наименьшее общее кратное) — это наименьшее натуральное число n такое, что n ··· a_{1}, n ··· a_{2}, …, n ··· a_{k}.

17. Пусть известны разложения чисел a и b на простые множители. Как найти их НОД и НОК.

18. Пусть a > 0, b > 0. Докажите, что НОД (a, b) · НОК (a, b) = ab.

19. Найдите НОК (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).

Сдать до 1 декабря.