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

Кружок 9-11 классов

Алгоритм Евклида. 2 октября 2010 года

0.

Докажите, что для любых натуральных чисел a и b, a ≥ b имеет место равенство (a, b) = (a − b, a). (Здесь и далее через (n, m) обозначен наибольший общий делитель чисел n и m.)

1.

Алгоритм Евклида. Пусть необходимо определить наибольший общий делитель двух натуральных чисел a = r₀ и b = r₁, r₀ > r₁. Произведем несколько делений с остатком:

r₀ = q₁ · r₁ + r₂;
r₁ = q₂ · r₂ + r₃;
...
r_i = q_{i + 1} · r_{i + 1} + r_{i + 2};
...
r_n = q_{n + 1} · r_{n + 1} + r_{n + 2}, где r_{n + 2} = 0.

Тогда утверждается, что (r₀, r₁) = r_{n + 1}.

a)

Докажите, что алгоритм Евклида содержит конечное число действий (делений) для любый a и b;

b)

Докажите, что (r₀, r₁) = (r₁, r₂).

с)

Поймите, что вы доказали, что (r₀, r₁) = (r_{n + 1}, r_{n + 2}) и что из этого следует, что (r₀, r₁) = r_{n + 1}.

Замечание. В алгоритме Евклида деление с остатком можно заменить вычитанием. Тогда нужно каждый раз вычитать из большего числа меньшее до тех пор, пока не получиться 0.

2.

Найдите наибольший общий делитель чисел 34 и 55, используя алгоритм Евклида.

3.

Обозначим через F_n n-ое число Леонардо Пизанского (более известные как числа Фибоначчи), т.е. F₁ = 1, F₂ = 1, а для каждого n ≥ 3 число F_n вычисляется по формуле F_n = F_{n − 1} + F_{n − 2}. Докажите, что (F_n , F_{n − 1}) = 1.

4.

В условиях алгоритма Евклида по индукции докажите, что все числа r₀, r₁, r₂, ..., r_n, r_{n + 1} можно представить в виде m · a + n · b для некоторых целых m и n.

Замечание. Следствием из предыдущей задачи явлется теорема о линейном представлении НОД: пусть d = (a, b), тогда существуют такие целые m и n, что m · a + n · b = d.

5.

С помощью алгоритма Евклида найдите линейное представление НОД чисел 34 и 55.

6.

Хулиган Ваня отобрал у милой девочки Маши открытку размерами m × n сантиметров и начал ее резать. Каждый раз он отрезает от открытки квадрат с максимально возможной стороной. Добрый преподаватель Максим Амирьянович отобрал у хулигана Вани остаток открытки, который имеет форму квадрата. С какой стороной?

7.

На прямой, в точке 0, сидит блоха. Каждый момент времени она прыгает в любом направлении (взад и вперед) на 2010 или 1447. В каких точках она может оказаться?

8.

Докажите, что для каждого натурального n дробь

12n + 1

30n + 2

несократима.

Указание

Указание. А на что она могла бы быть сократима?

9.

Докажите, что для всяких натуральных n и m выполнено равенство: (3ⁿ − 1 , 3^m − 1) = 3^{(n, m)} − 1.

10.

Руководство Малого Механико-Математического факультета выпустило в обращение купюры достоинством 65 и 999 мммфников. a) Докажите, что этими купюрами можно заплатить любую сумму денег (возможно, со сдачей). b) Докажите, что любую сумму большую 1000000 мммфников можно заплатить этими купюрами без сдачи.