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

Материал из Algocode wiki
Версия от 19:50, 10 февраля 2021; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

Определение:
Остаток от деления $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$.

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

Код на C++

const int mod = 1e9 + 7; // Поменяйте на тот, который в вашей задаче

template<typename T>
T add(T x) {
    return x;
}

template<typename T, typename... Ts>
T add(T x, Ts... y) {
    T res = x + add(y...);
    if (res >= mod)
        res -= mod;
    return res;
}
// Конструкция выше позволяет писать add(x, y, z, t, ...) с любым количеством аргументов 

template<typename T, typename... Ts>
T sub(T x, Ts... y) {
    return add(x, mod - add(y...));
}

// udd это add, записывающий результат сложения в первый аргумент. 
// Старое значение первого аргумента в сумме участвует
template<typename T, typename... Ts>
void udd(T &x, Ts... y) {
    x = add(x, y...);
}


template<typename T>
T mul(T x) {
    return x;
}

template<typename T, typename... Ts>
T mul(T x, Ts... y) {
    return (x * 1ll * mul(y...)) % mod;
}

template<typename T, typename... Ts>
void uul(T &x, Ts... y) {
    x = mul(x, y...);
}

int bin(int a, ll deg) {
    int r = 1;
    while (deg) {
        if (deg & 1)
            uul(r, a);
        deg >>= 1;
        uul(a, a);
    }
    return r;
}

// обратный по __простому__ модулю
int inv(int x) {
    assert(x);
    return bin(x, mod - 2);
}



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

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


Автор конспекта: Саша Гришутин

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