Арифметика по модулю

Основные определения

Сравнение по модулю - два целых числа считаются сравнимыми по модулю, если их разность делится на выбранный модуль. Это обычно записывают как $a \equiv b \pmod{n}$.

Остаток при делении - для любого целого числа существует представление в виде $a = nq + r$ , где $0 \le r < n$ . Остаток принято называть приведённым представителем класса сравнимости: $a \equiv r \pmod{n}$.

Понятие сравнения по модулю упрощает работу с большими числами: вместо того, чтобы оперировать значениями в обычной арифметике, мы можем заменить число его остатком при делении на модуль. Это даёт компактное представление, удобное для вычислений и доказательств. Свойства классов сравнимости и остатков формируют основу теории, применяемой как в теории чисел, так и в прикладных областях.

Операции и основные свойства

Сравнения по модулю совместимы с основными арифметическими операциями: если два числа сравнимы с парой других по одному и тому же модулю, то сумма и произведение этих чисел также сравнимы. Формально это звучит так: $a \equiv a'' \pmod{n},\quad b \equiv b'' \pmod{n}\ \Rightarrow\ a+b \equiv a''+b'' \pmod{n}$. Аналогично для произведения: $a \equiv a'' \pmod{n},\quad b \equiv b'' \pmod{n}\ \Rightarrow\ ab \equiv a''b'' \pmod{n}$. Важно отметить, что умножение на фиксированный множитель тоже сохраняет сравнимость: $a \equiv a'' \pmod{n} \ \Rightarrow\ ka \equiv ka'' \pmod{n}$.

Практически это значит, что при вычислениях можно сначала сократить множители или слагаемые по модулю, а затем выполнять операцию — результат совпадёт с тем, что дал бы прямой расчёт. Такая техника часто используется для упрощения сложных выражений, вычисления степеней по модулю и проверки делимости.

Обратимые элементы и критерий существования обратного

В кольце вычетов по модулю бывают элементы, обладающие мультипликативным обратным. Для целого элемента обратимость по модулю оказывается связана с наибольшим общим делителем. Критерий формулируется так: элемент обратим тогда и только тогда, когда $\gcd(a,n)=1$. В этом случае обратный x удовлетворяет сравнению $ax \equiv 1 \pmod{n}$ и обозначается как $a^{-1} \pmod{n}$.

Нахождение обратного обычно сводится к решению линейного диофантова уравнения, что удобно выполнять с помощью расширенного алгоритма Евклида. Обратимость имеет большое значение в криптографии и при решении линейных сравнений, поскольку без обратного не всегда удаётся разделить обе части сравнения.

Теоремы Эйлера и Ферма, вспомогательные результаты

Существуют мощные теоретические утверждения, которые упрощают вычисление степеней по модулю. Одно из ключевых — теорема Эйлера: при взаимной простоте основания и модуля выполняется $a^{\varphi(n)} \equiv 1 \pmod{n}$. Частный случай для простого модуля даёт маленькую теорему Ферма: $a^{p-1} \equiv 1 \pmod{p}$. Эти результаты позволяют существенно сокращать показатели степени при вычислениях по модулю.

Существуют и другие полезные факты, например теорема Уилсона, дающая характеристику простоты модуля через факториал: $(p-1)! \equiv -1 \pmod{p}$. Такие тождества часто используются при проверках простоты и разного рода оценках остатков.

Китайская теорема об остатках

Китайская теорема об остатках описывает ситуацию системы сравнений, когда модули попарно взаимно просты. Формулировка для двух сравнений выглядит как система $x \equiv a_1 \pmod{n_1}$ и $x \equiv a_2 \pmod{n_2}$. Если $N = n_1 n_2$, то существует единственное решение по модулю $N = n_1 n_2$.

Алгоритмически конструктивное решение строится через числа $N_i = \displaystyle\frac{N}{n_i}$, такие что для каждого индекса выполняется $N_i y_i \equiv 1 \pmod{n_i}$. Тогда общий вид решения можно записать как линейную комбинацию: $x \equiv \sum_{i} a_i N_i y_i \pmod{N}$, где сумма берётся по всем уравнениям системы, а итог берётся по модулю $N = n_1 n_2$.

Приложения и практические задачи

Арифметика по модулю находит множество прикладных применений: от простых задач на остатки в школьной программе до основ криптографических алгоритмов. В хешировании и проверочных суммах остатки по модулю используются для быстрого обнаружения ошибок. В криптографии повсеместно применяются теоремы о степенях и обратных элементах для построения ключевых операций.

В школьных задачах часто встречаются задачи вида «найти остаток», «решить линейное сравнение», «определить, существует ли решение системы сравнений». Для таких задач полезно уметь сокращать степени, применять критерий обратимости и уметь решать диофантовы уравнения методом Евклида. Важно также уметь формулировать рассуждения в терминах классов вычетов и приводить доказательства, опираясь на формулы и теоремы, приведённые выше.