Идеи и методы решения нестандартных задач: делимость и остатки

Делимость и остатки

Если числа a и b дают одинаковые остатки при делении на число m, то говорят, что a сравнимо с b по модулю m и записывают a ≡ b (mod m)

Два числа a и b сравнимы по модулю m тогда и только тогда, когда их разность делится на m. 5

Сравнения можно складывать и умножать. Если a ≡ b (mod m) и c ≡ d (mod m), n – произвольное целое положительное число, то a+c ≡ b+d (mod m), ac ≡ bd (mod m) и
aⁿ ≡ bⁿ (mod m). Таким образом определяется арифметика остатков или арифметика вычетов. В случае, если m = 10 приведённое утверждение особенно наглядно: чтобы найти последнюю цифру десятичной записи суммы (произведения), достаточно сложить (перемножить) последние цифры слагаемых (сомножителей) и взять последнюю цифру результата. Остаток может выступать в роли инварианта (например, остаток от деления на 9 в задачах про сумму цифр).

Пример 1. Докажите, что число n³ − n делится на 6 при всех целых n.

Решение. Разложим данное выражение на множители: n³ − n = (n − 1)n(n + 1). Мы получили произведение трёх последовательных целых чисел. Одно из них делится на 3, поэтому произведение делится на 3. По крайней мере одно из трёх последовательных чисел чётно, поэтому произведение чётно. Число, делящееся на 2 и 3, делится на 6.

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

Решение. Квадрат целого числа при делении на 8 даёт остаток 0, 1 или 4. Чтобы убедиться в этом достаточно проверить квадраты всевозможных остатков от деления на 8 – числа от 0 до 8. Но из трёх чисел вида 0, 1, 4 нельзя получить 7. Поэтому сумма трёх квадратов не может иметь остаток 7.

Пример 3. Докажите, что число, в десятичной записи которого участвуют три единицы и несколько нулей, не может быть квадратом.

Решение. Если такое число существует, то оно делится на 3, но не делится на 9 (по признакам делимости на 3 и 9). Но если число делится на 3 и является полным квадратом, то оно делится на 9. Противоречие.

Задачи для самостоятельного решения

1. Какие числа можно представить в виде разности двух квадратов целых чисел?

2. Если p – простое число, большее трёх, то p² −1 делится на 24.

3. При каких n число 2ⁿ − 1 делится на 7?

4. Известно, что сумма нескольких натуральных чисел делится на 6. Докажите, что сумма кубов этих чисел тоже делится на 6.

5. Докажите, что если целочисленная арифметическая прогрессия содержит квадрат целого числа, то она содержит бесконечно много квадратов целых чисел.

6. Три целых числа связаны соотношением x² + y² = z² . Докажите, что х или y делится на 3.

7. Шестизначное число делится на 7. Докажите, что, если последнюю его цифру переставить в начало, то полученное число тоже будет делиться на 7.

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

9. Докажите, что простые числа большие трёх можно записать в одном из двух видов: 6n + 1 либо 6n − 1, где n – натуральное число.

10. Докажите, что если сумма квадратов двух чисел делится на 3, то и каждое из этих чисел тоже делится на 3.

11. Дано натуральное число N. К нему справа приписывают по одной цифре, кроме девятки. Докажите, что рано или поздно получится составное число.

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

а) трёх кубов;

б) семи шестых степеней целых чисел.