Сравнения по модулю для задач на делимость⁠⁠

С ужасом обнаружил, что на пикабу нет статьи про такую прекрасную вещь, как сравнения по модулю и их применение в решении задач на делимость. А тем временем школьники страдают от сложности задачи "Найти, при каких натуральных n выражение n^4 + n^3 + n^2 + 2 делится на 4 без остатка или показать, что таких нет". Вне всяких сомнений особо шустрые школьники решат эту задачу, но сколько на это уйдёт времени? Я же предлагаю использовать метод сравнений по модулю, который в сущности своей довольно прост. В конце мы режим и эту задачу. Кстати, кажется, он может пригодиться даже на ЕГЭ. Итак.

Вспомним несколько простых фактов о делимости в Z. Собственно, иную и не рассматриваем. Поделить a на b (условимся рассматривать только целые числа) означает представить a как

a = bk + r, где r - остаток. На него накладываются определённые условия:
0 =< r < |b|. Важно запомнить, что остаток не может быть отрицательным, так что -9 равно не 4*(-2) - 1, а 4*(-3) + 3. Далее, при последовательном делении чисел на m получается m остатков со значениями 0, 1, ..., m - 1. Это всё простые вещи. Теперь новшества.

Два числа a и b называются сравнимыми по модулю m, если их разность нацело делится на m = два числа a и b называются сравнимыми по модулю m, если при делении на m они дают одинаковы остаток = два числа a и b называются сравнимыми по модулю m, если a = b + mk. Пишется это так:
a ≡ b (mod m)

Что там с примерами? Уже готовы.

7 ≡ 1 (mod 3)

12 ≡ 2 (mod 10)

4 ≡ -1 (mod 5)

Ну и зачем это? Сейчас всё будет. Для начала покажем некоторые свойства сравнений по модулю:

1. a ≡ a (mod m)

Док-во:

a - a = 0 - делится на m.

2. Если a ≡ b (mod m), а b ≡ c (mod m), то a ≡ c (mod m)

Док-во:
Если a ≡ b (mod m), то они дают при делении на m некий одинаковый остаток z. Из b ≡ c (mod m) следует, что c при делении на m даёт тот же остаток z. Отсюда уже по определению следует сравнимость a и c по модулю m.

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

Док-во:
Сами докажите и не забудьте ещё про разность. Мне лень. :)

4. Если a ≡ b (mod m), то ah ≡ bh (mod m), где h - целое число.

Док-во:
Из сравнимости следует, что

a - b = mk

Домножим обе части на целое число h
ah - bh = mkh

Вот тут можно как перейти к модулю mh, так и остаться в модуле m. Мы останемся, так что воспользуемся ассоциативностью умножения в кольце (Z, +, *) и очевидной замкнутостью относительно * (это, впрочем, следует из определения кольца):
ah - bh = m(kh)

ah - bh = mg, где g = kh - целое число

Итак, мы получили, что ah - bh делится на m с нулевым остатком. Следовательно?..

5. Если a ≡ b (mod m), то a^n ≡ b^n (mod m), где n - натуральное число.

Док-во:
Так хочется полежать...

6. Ну тут сами или загляните в википедию. Я и так написал слишком много, чтобы изобрести уже два велосипеда. Вы совершенно справедливо заметите, если скажете, мол, хватит нам пудрить мозги - давай уже за дело. Даю...

Но! Сперва я введу ещё одну структуру - класс вычетов по модулю m. Чтобы объяснить взаимозаменяемость, которой мы позже коснёмся. :)

Будем последовательно делить на m, отвлекаясь от неполного/полного частного. Нас интересуют только остатки от деления. Скажем, будем последовательно делить на 4 (из дидактических соображений не увожу в область отрицательных чисел) и искать значение числовой функции Rest, которая выдаёт остатки от деления:

Rest(0; 4) = 0

Rest(1; 4) = 1

Rest(2; 4) = 2

Rest(3; 4) = 3

Rest(4; 4) = 0

Rest(5; 4) = 1

Rest(6; 4) = 2

Rest(7;4) = 3

...

Далее получится 0 и снова будут повторяться остатки. Цикл замкнулся. Далее заметим, что числа с равными остатками в общем виде представимы как a = 4k + r, где r принадлежит множество {0, 1, 2, 3} [ мы берём модуль 4, то есть делим на 4]. Эти числа разбивают всё множество Z на определённые группы чисел, которые имеют одинаковые остатки при делении на 4. Обобщим это на любой модуль m: последовательное деление на m разбивает множество Z на классы чисел, дающие при делении на m одинаковый остаток. Эти числа, очевидно, сравнимы по модулю m. Такие классы называются классами вычетов по модулю m. Их всего будет m штук. Множество классов вычетов по модулю m обозначается как G(m). Образуем, примера ради, множество G(2). Итак, всего будет 2 класса вычетов, причём они будут сравнимы по модулю 2 с числам 0 и 1. Если обозначить класс вычетов по модулю m как [k], где k - наименьший положительный вычет, то получатся два класса:
[0] = {2l}

[1] = {2l + 1}

Тогда G(2) = {[0], [1]}

Таким образом классы вычетов суть множества (классы, если точнее). Зачем они нам? В нашем случае - на самом деле это очень богатая структура - они позволяют взаимозаменять числа, сравнимые по модулю m, ибо тогда они попадут в один класс вычетов по модулю m. Иными словами, все числа из одного класса вычетов по модулю m тождественны при решении задач на остатки. Вот теперь мы готовы к задачам.

1. При каких натуральных n выражение n^2 + 2 делится на 2 без остатка?

Решение:
Переформулируем задачу на языке сравнений по модулю 2:
n^2 + 2 ≡ 0 (mod 2)

Будем смотреть на n в упор, для которого существует всего два случая:
1. n ≡ 0 (mod 2)

Далее возводим в квадрат обе части сравнения:
n^2 ≡ 0 (mod 2)

И прибавляем 2:

n^2 + 2 ≡ 0 (mod 2)

Многие здесь недоумевают, почему n^2 + 2 ≡ 0 (mod 2), а не n^2 + 2 ≡ 0 (mod 2). На самом деле всё просто: прибавляя к обеим частям число вида ml, где m - модуль сравнения, правая или левая часть не меняется, "счётчик обнуляется" (подумайте почему, см. остатки и определение сравнения).

2. n ≡ 1 (mod 2)

n^2 ≡ 1 (mod 2)

n^2 + 2 ≡ 1 (mod 2)

Итак, наше требование выполняется только при n ≡ 0 (mod 2), то есть n = 2k -чётном натуральном числе. Записывайте ответ.

2. Доказать, что a^n + b^n, где n - натуральное число, делится на a - b без остатка.

Решение:
Нужно доказать, что a^n + b^n ≡ 0 (mod a - b)

Давайте с галёрки:

a ≡ b (mod a - b) - проверьте!

a^n ≡ b ^n (mod a - b)

a^n - b^n ≡ 0 (mod a - b)

ЧТД.

3. Найти последнюю цифру 17^2132

Решение:

Нас просят найти x с условием 17^2132 ≡ x (mod 10)

Идём с галёрки:
17^2132 ≡ 7^2132 [помните про классы вычетов???] (mod 10)

Далее замечаем 7^4 = 2401 ≡ 1 (mod 10)

7^2132 = (7^4)^533 ≡ 1^533 = 1 (mod 10)

Итак, последняя цифра 1.

4. Решим предложенную в самом начале задачу.

Решение:

Нам нужно рассмотреть 4 случая и вытащить 4 сравнения.

1)
n ≡ 0 (mod 4)

n^2 ≡ 0 (mod 4)

n^3 ≡ 0 (mod 4)

n^4 ≡ 0 (mod 4)

n^4 + n^3 + n^2 + n ≡ 0 (mod 4) - сложили сравнения

n^4 + n^3 + n^2 + n + 2 ≡ 2 (mod 4) - не подходит: остаток 2

2)

...

Ну, вы поняли! :)

Пусть это будет домашним заданием, а я на этом заканчиваю. Вот.