МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Занятие 4. Алгоритм Евклида

Определение. Наибольший общий делитель целых чисел a и b — это наибольшее натуральное число c такое, что a делится на c и b делится на c. Обозначается НОД(a, b) или просто (a, b). Аналогично определяется НОД нескольких целых чисел. Целые числа a и b называются взаимно простыми, если НОД(a, b) = 1.

Во всех задачах этого занятия латинскими буквами обозначаются целые числа (и даже натуральные, если не оговаривается иное).

1.

Пусть a ≥ b. Докажите, что НОД(a, b) = НОД(a − b, b).

2.

(шаг алгоритма Евклида) Пусть a и b — натуральные числа и a > b. Поделим a и b c остатком: a = bq + r, 0 ≤ r < b. Докажите, что НОД(a, b) = НОД(b, r).

Алгоритм Евклида. Для вычисления НОД(a, b) начнём с пары чисел (a, b) и будем применять шаги, описанные в предыдущей задаче. При каждом переходе от пары (делимое, делитель) к паре (делитель, остаток) оба числа в паре уменьшаются, а их НОД сохраняется. В некоторый момент получим пару (d, 0), где d = НОД(a, b).

3.

Не раскладывая числа на простые множители, вычислите:

a)

НОД(861, 637)

б)

НОД(2014, 7813)

в)

НОД(121, 759)

4.

Сократите дробь \( \frac{5840383}{34173679} \).

5.

Найдите:

a)

НОД(n, n + 1)

б)

НОД(2n, 2n + 2)

в)

НОД(3n, 6n + 3)

г)

НОД(2n + 13, n + 7)

6.

На доске написаны числа a и b. Ваня заменяет одно из чисел на сумму или разность написанных чисел. Какое минимальное натуральное число он может получить за несколько таких операций, если:

a)

a = 1001, b = 759;

б)

a = 7n + 3, b = 11n + 5.

7.

Возьмём прямоугольник m×n клеточек и будем раз за разом отрезать по клеточкам от него квадрат с максимально возможной стороной. В итоге получится квадрат. С какой стороной?

8.

Найдите:

а)

НОД(10⁷ − 1, 10⁵ − 1);

б)

НОД(11…1 (m единиц), 11…1 (n единиц));-

в)

НОД(a^m − 1, aⁿ − 1).

9.

Докажите, что НОД(5a + 3b, 13a + 8b) = НОД(a, b).