Задача 85:

Пусть ka ≡ kb (mod %)%m, k и m – взаимно просты. Тогда a ≡ b (mod %)%m.

Решение:

Поскольку ka ≡ kb (mod %)%m, то ka – kb = k(a – b) делится на m. Так как k и m взаимно просты, то a – b делится на m, т.е. a ≡ b (mod %)%m.

Задача 86:

Пусть ka ≡ kb (mod kn). Тогда a ≡ b (mod %)%n.

Решение:

ka – kb делится на kn, т.е. k(a – b) = mkn. Следовательно, a – b = mn, ч.т.д.

Задача 87:

Найдите остаток от деления 2¹ºº на 101.

Решение:

Вследствие малой теоремы Ферма, он равен 1.

Задача 88:

Найдите остаток от деления 3¹º² на 101.

Решение:

Так как 101 – простое число, то 3¹ºº ≡ 1 (mod 101). Отсюда 3¹º² ≡ 9 • 3¹ºº = 9 (mod 101).

Задача 89:

Докажите, что 300³ººº – 1 делится на 1001.

Решение:

300³ººº = (300⁵⁰⁰)⁶ ≡ 1 (mod 7). Аналогично, 300³ººº ≡ 1 (mod 11) и  (mod 13). Следовательно, 300³ººº – 1 делится и на 7, и на 11, и на 13, т.е. на 1001.

Задача 90:

Найдите остаток от деления 8⁹⁰⁰ на 29.

Решение:

7.

Задача 91:

Докажите, что 7¹²º – 1 делится на 143.

Решение:

Докажем, что 7¹²º – 1 делится на 11 и на 13. Действительно, (7¹²)¹º ≡ 1 (mod 11) и (7¹º)¹² ≡ 1 (mod 13).

Задача 92:

Докажите, что число 30²³⁹ + 239³º – составное.

Решение:

Это число делится на 31.

Задача 93:

Пусть p – простое число. Докажите, что (a + b)^p = a^p + b^p (mod %)%p для любых целых a и b.

Решение:

(a + b)^p ≡ (a + b) = a + b ≡ a^p + b^p (mod p).

Задача 94:

Сумма трех чисел a, b и c делится на 30. Докажите, что a⁵ + b⁵ + c⁵ также делится на 30.

Решение:

Докажите, что для произвольного целого x верно сравнение x⁵ ≡ x (mod 30).

Задача 95:

Пусть p и q – различные простые числа. Докажите, что

а) p^q + q^p = p + q (mod pq).

б) – четное число, если p, q ≠ 2.

Решение:

Докажите, что p^q + q^p – p – q делится и на p, и на q.

Задача 96:

Пусть p – простое число, и a не делится на p. Докажите, что найдется натуральное число b, для которого ab ≡ 1 (mod p).

Решение:

Положите b = a^p – 2.

Задача 97:

(Теорема Вильсона). Пусть p – простое число. Докажите, что (p – 1)! ≡  – 1 (mod %)%p.

Задача 98:

Пусть n – натуральное число, не кратное 17. Докажите, что либо n⁸ + 1, либо n⁸ – 1 делится на 17.

Решение:

(n⁸ + 1)(n⁸ – 1) = n¹⁶ – 1 = 0 (mod 17).

Задача 99:

а) Пусть p – простое число, отличное от 3. Докажите, что число 111 … 11 (p единиц) не делится на p.

б) Пусть p > 5 – простое число. Докажите, что число 111 … 11 (p – 1 единица) делится на p.

Решение:

а) 111 … 11 (p единиц)  = (10^p – 1)/9, а 10^p – 1 не делится на p, так как 10^p – 1 ≡ 10 – 1 = 9 (mod p).

б) 111 … 11 (p – 1 единица)  = (10^p – 1 – 1)/9, а 10^p – 1 – 1 делится на p, так как p взаимно просто с 10 и с 9.

Задача 100:

Докажите, что для любого простого p разность 111 … 11222 … 22333 … 33 … 888 … 88999 … 99 – 123456789 (в первом числе каждая ненулевая цифра написана p раз) делится на p.

Решение:

Воспользуйтесь тем, что 10^p ≡ 10 (mod p), 10^2p ≡ 100 (mod p), …, 10^8p ≡ 10⁸ (mod p).