Задача 1:

Докажите, что a ≡ b (mod m) тогда и только тогда, когда a – b делится на m.

Решение:

Пусть a ≡ b (mod m). Обозначим одинаковый для a и b остаток при делении на m через r. Тогда

Отсюда a – b = m(k₁ – k₂) делится на m.

Обратно, пусть a – b делится на m. Разделим a и b на m с остатком. Получим a = mk₁ + r₁, b = mk₂ + r₂. Отсюда a – b = m(k₁ – k₂) + r₁ – r₂ делится по условию на m. Таким образом, r₁ – r₂ делится на m. Так как |r₁ – r₂| < m, то r₁ = r₂.

Задача 2:

Если a ≡ b (mod m) и c ≡ d (mod %)%m, то a + c ≡ b + d (mod %)%m.

Решение:

Так как a – b делится на m и c – d делится на m, то (a – b) + (c – d) = (a + c) – (b + d) делится на m, что и требовалось доказать.

Задача 3:

Если a ≡ b (mod %)%m и c ≡ d (mod %)%m, то a – c ≡ b – d (mod %)%m.

Задача 4:

Если a ≡ b (mod %)%m и c ≡ d (mod %)%m, то ac ≡ bd (mod %)%m.

Решение:

ac – bd = ac – bc + bc – bd = (a – b)c + b(c – d) делится на m, что и требовалось доказать.

Задача 5:

Если a ≡ b (mod %)%m, n – натуральное число, то aⁿ ≡ bⁿ (mod %)%m.

Задача 6:

Докажите, что n² + 1 не делится на 3 ни при каком целом n.

Решение:

Ясно, что каждое целое число n сравнимо по модулю 3 либо с 0, либо с 1, либо с 2.

Если n ≡ 0 (mod %)%3, то n² ≡ 0 (mod 3) – (умножение сравнений) и n² + 1 ≡ 1 (mod %)%3 – (сложение сравнений).

Если n ≡ 1 (mod %)%3, то n² + 1 ≡ 2 (mod %)%3.

Если n ≡ 2 (mod %)%3, то n² + 1 ≡ 2 (mod %)%3.

Таким образом, ни в одном случае мы не получим n² + 1 ≡ 0 (mod %)%3.

Задача 7:

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

Решение:

Заметим, что 6 ≡  – 1 (mod %)%7. Возводя это сравнение в сотую степень, получаем 6¹ºº ≡ ( – 1)¹ºº (mod %)%7, то есть 6¹ºº ≡ 1 (mod %)%7.

Задача 8:

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

Решение:

30⁹⁹ ≡ ( – 1)⁹⁹ ≡  – 1 (mod 31) 61¹ºº ≡ ( – 1)¹ºº ≡ 1 (mod 31).

Задача 9:

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

а) 43¹º¹ + 23¹º¹ делится на 66.

б) aⁿ + bⁿ делится на a + b, если n – нечетное число.

Решение:

б) aⁿ + bⁿ = (a + b)(a^n – 1 – a^n – 2b +  …  + ( – 1)^n – 1b^n – 1)

Задача 10:

Докажите, что 1ⁿ + 2ⁿ +  …  + (n – 1)ⁿ делится на n при нечетном n.

Решение:

Указание: Рассмотрите сумму симметричных слагаемых.

Задача 11:

Докажите, что существует бесконечно много натуральных чисел, не представимых в виде суммы трех точных кубов.

Решение:

Рассмотрите числа вида 8k + 7.

Задача 12:

Докажите, что ни одно из чисел вида 10^3n + 1 нельзя представить в виде суммы двух кубов натуральных чисел.

Решение:

Куб натурального числа сравним по модулю 7 либо с 0, либо с 1, либо с  – 1 – проверьте! Поэтому сумма двух кубов сравнима с одним из следующих чисел:  – 2,  – 1, 0, 1, 2. Заметим, что 10 ≡ 3 (mod %)%7, а 10³ ≡  – 1 (mod %)%7. Поэтому 10^3n + 1 сравнимо либо с 3, либо с  – 3 по модулю 7.

Задача 13:

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

Решение:

Используйте тождество x² – y² = (x – y)(x + y).

Задача 14:

Назовем натуральное число n удобным, если n² + 1 делится на 1000001. Докажите, что среди чисел 1, 2, …, 1000000 четное число удобных.

Решение:

Если x – удобное число, то и 1000001 – x – также удобное.

Задача 15:

а) Может ли квадрат натурального числа оканчиваться на 2?

б) Можно ли, используя только цифры 2, 3, 7, 8 (возможно, по несколько раз), составить квадрат натурального числа?

Решение:

а) нет; б) нет.

Задача 16:

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

Решение:

Например,  – 1 или n – 1.

Задача 17:

Найдите остаток от деления на 7 числа 10¹º + 10¹ºº + 10¹ººº +  …  + 10¹ºººººººººº.

Решение:

5.

Задача 18:

Сколько существует натуральных чисел n, меньших 10000, для которых 2ⁿ – n² делится на 7?

Решение:

2858.

Задача 19:

Обозначим через k произведение нескольких (больше одного) первых простых чисел. Докажите, что число а) k – 1; б) k + 1 не является точным квадратом.

Решение:

а) k – 1 = 3p + 2, а по модулю 3 квадраты могут давать лишь остатки 0 или 1.

б) k + 1 = 4q + 3, а по модулю 4 квадраты могут давать лишь остатки 0 или 1.

Задача 20:

Существует ли такое натуральное n, что n² + n + 1 делится на 1955?

Решение:

Нет. n² + n + 1 не может даже делиться на 5.

Задача 21:

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

Решение:

Задача 22:

Пусть n – натуральное число такое, что n + 1 делится на 24. Докажите, что сумма всех натуральных делителей n делится на 24.

Решение:

Докажите, что сумма делителей делится и на 3, и на 8.

Задача 23:

Последовательность a₁, a₂, a₃, … натуральных чисел такова, что a_n + 2 = a_n + 1a_n + 1 при всех n.

а) a₁ = a₂ = 1. Докажите, что ни один из членов последовательности не делится на 4.

б) Докажите, что a_n – 22 – составное число при любом n > 10.

Решение:

а) Рассмотрите остатки членов последовательности по модулю 4 и докажите, что они повторяются по циклу. б) a_n – 22 делится на a_n – 6.