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

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

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

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

Если числа n и m имеют одинаковый остаток от деления на k, их называют сравнимыми по модулю k. Записывается это так: n ≡ m (mod k). В прошлом листочке разссказывалось про такое свойство: если a₁ ≡ a₂ (mod k) и b₁ ≡ b₂ (mod k), то и a₁ + b₁ ≡ a₂ + b₂ (mod k), a₁ · b₁ ≡ a₂ · b₂ (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) = НОД(a − b,b).

4.

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

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

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

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

Найдите НОД а) 10⁷ − 1 и 10⁵ − 1; б) 11...1 (n единиц) и 11...1 (m единиц); в) a^m − 1 и aⁿ − 1.

7.

Докажите, что при любых натуральных n дробь

12n + 1

30n + 1

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

8.

Вася и Петя нашли на дороге по пачке 11-рублевок. В чайной Вася выпил 3 стакана чая, съел 4 калача и 5 бубликов. Петя выпил 9 стаканов чая, съел 1 калач и 4 бублика. Стакан чая, калач и бублик стоят по целому числу рублей. Оказалось, что Вася может расплатиться 11-рублевками без сдачи. Покажите, что это может сделать и Петя.