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

Руководители Фируза Исамитдиновна Мамедова и Александра Ефремовна Подгайц
2012/2013 учебный год

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

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

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

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

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

1.
Найдите НОД а) 1313 и 13953; б) 107 − 1 и 105 − 1; в) \(\underbrace{11\ldots111}_{m}\) и \(\underbrace{11\ldots111}_{n}\); г) an − 1 и am − 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.
Обозначим через Fn n-ое число Фибоначчи, т.е. F1 = 1, F2 = 1, а для каждого n ≥ 3 число Fn вычисляется по формуле Fn = Fn − 1 + Fn − 2. Докажите, что (Fn , Fn − 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 мммфников можно заплатить этими купюрами без сдачи.