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

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

Руководители А. С. Воропаев, П. С. Дергач, Ф. И. Мамедова и Ю. А. Цимбалов
2011/2012 учебный год

Версия для печати

Теория чисел — 3

Алгоритм Евклида

Если числа n и m имеют одинаковый остаток от деления на k, их называют сравнимыми по модулю k. Записывается это так: nm (mod k). В прошлом листочке разссказывалось про такое свойство: если a1a2 (mod k) и b1b2 (mod k), то и a1 + b1a2 + b2 (mod k), a1 · b1a2 · b2 (mod k). Это позволяет, например, проделывать такое: если мы рассматриваем сравнение по модулю 7, то 13³· 8 + 702² ≡ ( − 1)³· 1 + 2² ≡ 3 (mod 7).

1.
Найдите остаток от деления 56·30 + 41 на 11.
2.
Найдите остаток от деления 111·425·2424 на 37.
3.
Найдите какое-нибудь нечётное натуральное число, которое имеет остаток 2 при делении на три, остаток 3 при делении на четыре, 4 при делении на пять и 5 при делении на шесть.

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

4.
Докажите, что НОД(a,b) = НОД(ab,b). Это можно сделать например так: доказать, что у этих пар чисел одинаковые наборы общих делителей, откуда следует, что и наибольшие из общих делителей у них одинаковые.

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

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

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

Пример 2. (413523,1443) = (825,1443) = (825,618) = (207,618) = (207,204) = (3,204) = 3

5.
Найдите НОД а) 142 и 235; б) 1313 и 13953.
6.
Найдите НОД а) 107 − 1 и 105 − 1; б) 11...1 (n единиц) и 11...1 (m единиц); в) am − 1 и an − 1.
7.
Докажите, что при любых натуральных n дробь
12n + 1
30n + 1
несократима.
8.
Вася и Петя нашли на дороге по пачке 11-рублевок. В чайной Вася выпил 3 стакана чая, съел 4 калача и 5 бубликов. Петя выпил 9 стаканов чая, съел 1 калач и 4 бублика. Стакан чая, калач и бублик стоят по целому числу рублей. Оказалось, что Вася может расплатиться 11-рублевками без сдачи. Покажите, что это может сделать и Петя.

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