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

Кружок 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 мммфников можно заплатить этими купюрами без сдачи.

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS