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

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

Занятие 2. Сравнения по модулю

Определение. Целые числа a и b называются сравнимыми по модулю m, если они имеют одинаковые остатки при делении на m. То есть a ≡ b (mod m), если a = q₁ · m + r и b = q₂ · m + r, где 0 ≤ r < m, где m — натуральное число, а a, b, q — целые.

Базовое свойство: a ≡ b (mod n) ⇔ n | (a − b).

Основные свойства сравнений по модулю:
а) если a ≡ b (mod m) и b ≡ c (mod m), то a ≡ c (mod m);
б) если a ≡ b (mod m) и c ≡ d (mod m), то a + c ≡ b + d (mod m);
в) если a ≡ b (mod m) и c ≡ d (mod m), то a − c ≡ b − d (mod m);
г) если a ≡ b (mod m) и c ≡ d (mod m), то a · c ≡ b · d (mod m);
д) если a ≡ b (mod m) и n — натуральное число, то aⁿ ≡ bⁿ (mod m).

1.

Найдите наименьшее натуральное число, которое сравнимо:

а)

с 17 + 23 по модулю 29;

б)

c 42 − 67 по модулю 71;

в)

с 1 + 2 + 3 + … + 49 + 50 по модулю 51.

2.

Найдите остаток от деления:

а)

8¹⁰⁰ на 7;

б)

8¹⁰⁰ на 9;

в)

8²⁰¹⁵ на 11.

3.

Докажите, что

а)

30⁹⁹ + 61¹⁰⁰ ⋮ 31;

б)

43⁹⁹ + 23⁹⁹ ⋮ 33;

в)

3¹⁰⁰ − 2¹⁰⁰ ⋮ 5.

4.

Найдите остаток от деления 9¹²¹ + 13¹²¹ на 11.

5.

Докажите, что 8¹⁰¹ + 8¹⁰² + … + 8¹⁰⁷ ≡ 0 (mod 7).

6.

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

7.

Докажите, что число 1 · 2 · 3 · … · 443 + 444 · 445 · 446 · … · 886 делится на 887.

8.

Докажите, что 11ⁿ + 2 + 12^{2n + 1} делится на 133 при любом натуральном n.

9.

Докажите, что при любом натуральном n число (2ⁿ − 1)ⁿ − 3 делится на 2ⁿ − 3.

10.

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