Модульная арифметика

Модульная арифметика

Говоря о теории чисел, мы будем работать с остатками.

Определение:
Остаток от деления $a$ на $b$ —это такое число $0 \le c < b$, что $a = bq + c$ для некоторого $q$.

Выражение $a \equiv b \pmod m$ означает, что остатки от деления $a$ на $m$ и $b$ на $m$ равны. Это выражение читается как «$a$ сравнимо $b$ по модулю $m$».

Еще это можно опрделить так: $a$ сравнимо c $b$ по модулю $m$, если $(a - b)$ делится на $m$.

Все целые числа можно разделить на классы эквивалентности — два числа лежат в одном классе, если они сравнимы по модулю $m$. Говорят, что мы работаем в «кольце остатков по модулю $m$», и в нем ровно $m$ элементов: $0, 1, 2, \cdots, m-1$.

Сложение, вычитение и умножение по модулю определяются довольно интуитивно — нужно выполнить соответствующую операцию и взять остаток от деления.

Некоторые свойства:

1. $a \equiv b$, $c \equiv d \Rightarrow a \pm c \equiv b \pm d \mod m$
2. $a \equiv b$, $c \equiv d \Rightarrow ac \equiv bd \mod m$
3. $a\equiv b \mod m \Rightarrow a^n \equiv b^n \mod m$

Деление по модулю

Поделить одно число $a$ на другое число $b$ в кольце вычетов по модулю $m$ — значит найти такое число $c$, что $cb \equiv a \mod m$. Эта задача уже сложнее, чем сложение и умножение по модулю. Она сводится у нахождению так называемого обратного по модулю к числу $b$.

Обратным к числу $a$ по модулю $m$ называют такое число $a^{-1}$, что $a\cdot a^{-1} \equiv 1 \mod m$.

В том случае, если модуль простой (является простым числом), найти обратный всегда можно, только если исходное число не делится на модуль $m$. Если же модуль — составное число, то обратный элемент к $a$ существует только тогда, когда $(a, m) = 1$, то есть когда $a$ и $m$ взаимнопросты.

Утверждение: (Существование обратного)
Обратный элемент существует только для чисел, взаимно простых с модулем

Доказательство:
Сначала покажем, что для взаимно простого с $m$ числа обратный всегда найдется. Так как мы работаем только с остатками по модулю $m$, то будем считать одним и тем же объектом число и его остаток.

Рассмотрим числа $0\cdot a, 1\cdot a, ... , (m-1)\cdot a$. Поймем, что это различные остатки по модулю $m$. Допустим, есть два одинаковых и это $xa$ и $ya$. Тогда $a(x - y) \equiv 0 \mod m$. Но так как $(a, m) = 1$, то $x - y \equiv 0 \mod m$. Но оба числа $x, y$ лежат на отрезке $[0, m-1]$. Так как их разность сравнима с нулем, то они могут быть только одинаковыми числами, иначе их разность будет находиться в отрезке $[1, m-1]$. Значит, все остатки различны. Так как их $m-1$ штука, то обязательно встретится остаток $1$. То есть найдется $ka \equiv 1 \mod m$ — обратный по модулю $m$ к числу $a$.

Теперь покажем, что для чисел, не взаимно простых с $m$, обратного не существует. Пусть $(a, m) = b > 1$. Тогда если есть обратный, то $aa^{-1} \equiv 1 \mod m$.

$a = bt, \ m = bp$

$bta^{-1}-1=bp \Rightarrow b\left(ta^{-1} - p\right) = 1 \Rightarrow b \mid 1$ — противоречие.

Значит, обратный элемент существует для тех и только тех элементов, которые взаимно просты с модулем $m$.

Если мы нашла обратное к $b$ число, то $ab^{-1} \equiv bcb^{-1} \equiv c \mod m$. То есть умножив $a$ на обратное к $b$ число, мы выполнили деление и нашли искомое $c$.

О том, как искать обратный по модулю читайте в отдельной статье.

---

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko