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

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

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

Остатки (29 октября 2011 года)

Если числа n и m имеют одинаковый остаток от деления на k, то их называют сравнимыми по модулю k. Записывается это так: n ≡ m (mod k). (Если понятно, какой модуль имеется в виду, то скобку для краткости опускают.)

Пример 1. 2 ≡ 7 (mod 5); 11 ≡ 301 (mod 10); 5 ≡ − 4 (mod 9).

Чтобы узнать, сравнимы ли два числа по модулю k, достаточно проверить, делится ли их разность на k.

1.

Докажите это.

Сравнение по модулю обладает замечательным свойством, связанным со сложением: если a ≡ b (mod k) и c ≡ d (mod k), то a + c ≡ b + d (mod k). Доказать это просто: раз (a − b) и (c − d) делятся на k, то и их сумма (a − b) + (c − d) = (a + c) − (b + d) делится на k, что и означает, что a + c и b + d имеют одинаковый остаток при делении на k.

Пример 2. 4414 + 14757 ≡ 4 + 2 ≡ 1 (mod 5)
Пример 3. 300 − 151 ≡ 0 − 1 ≡ 2 (mod 3)

Часто помогает такая запись: если a ≡ b (mod k), то можно записать, что для некоторого целого числа n (возможно, нулевого или отрицательного) a = b + kn. Например, свойство о сложении можно доказать так: a + c = b + kn + d + km = b + d + k·(n + m) ≡ b + d (mod k)

2.

Докажите, что у сравнения по модулю есть такое же свойство с умножением.

3.

Найдите остаток от деления 99993 + 90995 на 9.

4.

Найдите остаток от деления 133·90 на 11.

5.

Найдите остаток от деления а) 35·35; б) 35· 35· 35; в) 35³⁵ на 3.

6.

Найдите остаток от деления 7³⁴³⁵ на 8.

7.

Докажите, что 30⁹⁹ + 63⁹ делится на 31.

8.

Докажите, что aⁿ + bⁿ делится на a + b при всех нечётных n.

9.

Докажите, что 1¹⁷ + 2¹⁷ + … + 16¹⁷ делится на 17.

10.

Какое число нужно прибавить к (n² + 1)¹⁰⁰⁰(n³ − 1)¹⁰⁰¹, чтобы результат делился на n?

11.

Докажите, что 5ⁿ + 1 не делится на 5^m − 1 ни при каких натуральных n и m.

12.

При каких n можно разложить n яблок по 10 корзинам так, чтобы число яблок в соседних корзинах отличалось ровно на 1?

13.

Докажите, что среди 51 целого числа найдутся два, квадраты которых имеют одинаковый остаток при делении на 100.