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

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

Теория чисел — Алгоритм Евклида

Быстрый и простой способ найти НОД (наибольший общий делитель) двух чисел — действовать по алгоритму Евклида. Он основан на том, что НОД(a,b) = НОД(a × b, b).

Алгоритм Евклида работает так: на каждом шаге от пары чисел a > b мы переходим к паре a − b и b, то есть от большего числа отнимаем меньшее. Продолжим этот процесс. Так как числа никогда не будут отрицательными, и всегда будут натуральными, то процесс не может продолжаться вечно. А когда он остановится? А только тогда, когда числа в паре станут одинаковыми. Когда это произойдёт, найти их НОД уже не будет составлять никакого труда.

Пример. НОД(511, 292) = НОД(219, 292) = НОД(219, 73) = НОД(146, 73) = НОД(73, 73) = 73.

Ещё более упростить процесс помогает такое соображение: когда несколько раз вычитаем из большего числа меньшее: a − b, a − 2b, a − 3b, то остановимся мы тогда, когда число из большего наконец станет меньшим, например так: a − 4b < b. Но тогда a = 4b + (a − 4b), то есть a − 4b это остаток от деления a на b. Так что можно было не расписывать все a − b, a − 2b и т.д., а сразу заменить a на остаток от деления a на b. Часто это оказывается быстрее, чем много раз вычитать.

1.

Найдите НОД а) 1313 и 13953; б) 10⁷ − 1 и 10⁵ − 1; в) \(\underbrace{11\ldots111}_{m}\) и \(\underbrace{11\ldots111}_{n}\); г) aⁿ − 1 и a^m − 1.

2.

На какое число и при каких натуральных n сократима дробь \(\dfrac{3n+4}{2n+5}\)?

3.

Докажите, что следующие дроби несократимы при всех натуральных значениях n: а) \(\frac{2n+13}{n+7}\); б) \(\frac{2n^2-1}{n+1}\); в) \(\frac{n^2-n+1}{n^2+1}\);

4.

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

5.

Обозначим через 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.

6.

(Про часы) Существует ли в сутках момент, когда часовая, минутная и секундная стрелки правильно идущих часов образуют попарно углы 120 градусов?

7.

Докажите, что для нечетных чисел a, b и c имеет место равенство: \[\mbox{НОД}(\frac{a+b}{2},\frac{b+c}{2},\frac{a+c}{2})=\mbox{НОД}(a,b,c).\]

8.

Руководство Малого Механико-Математического факультета выпустило в обращение купюры достоинством 65 и 999 мммфников.

a)

Докажите, что этими купюрами можно заплатить любую сумму денег (возможно, со сдачей).

б)

Докажите, что любую сумму большую 1000000 мммфников можно заплатить этими купюрами без сдачи.