Что такое обратное число?
Как вы помните, если некое число умножить на число, обратное ему, то получится 1. Из основ арифметики мы знаем следующее:
- Числом, обратным к числу A, называется такое число 1/A, что A * 1/A = 1 (то есть, к примеру, для числа 5 обратным будет 1/5).
- У каждого вещественного числа, кроме 0, есть обратное.
- Умножение на число, обратное A, эквивалентно делению на A (то есть, к примеру, 10/5 — это то же, что 10* 1/5).
Что такое обратное число по модулю?
В модульной арифметике нет операции деления, но есть обратные числа.
-
Число, обратное A (mod C), обозначается A^-1.
-
(A * A^-1) ≡ 1 (mod C) , или, что то же самое, (A * A^-1) mod C = 1.
-
Только у чисел, взаимно простых с C (то есть у тех, у которых нет с C общих простых делителей), есть обратные (mod C)
Как найти обратное число по модулю
Самый
простой метод
нахождения обратного числа к A (mod C) выглядит следующим образом:
Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1.
Шаг 2. Обратным числом для A mod C будет являться такое B, для которого A * B mod C = 1
Обратите внимание, что B mod C может принимать значения от 0 до C-1, поэтому нет смысла проверять числа, бо́льшие чем B.
Пример: A=3, C=7
Шаг 1. Вычисляем A * B mod C для значений B от 0 до C-1
3 * 5 ≡ 15 (mod 7) ≡
1
(mod 7) <—— ОБРАТНОЕ НАЙДЕНО!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
5 — это обратное значение для 3 mod 7, поскольку 5*3 mod 7 = 1.
Давайте рассмотрим другой пример, где обратного значения нет.
Пример: A=2, C=6
Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1**
Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
Таких значений B, при которых A * B mod C = 1, не существует. Следовательно, у числа A нет обратного значения (mod 6).
Всё дело в том, что числа 2 и 6 не являются взаимно простыми (у них есть общий простой делитель 2).
Кажется, что этот метод слишком медленный…
Есть более быстрый способ нахождения обратного значения для A (mod C), который мы и обсудим в следующих статьях, посвящённых расширенному алгоритму Евклида.
Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.
Обратный элемент по модулю
Часто в задачах требуется посчитать что-то по простому модулю (чаще всего (10^9 + 7)). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.
Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:
c = (a + b) % mod;
c = (mod + a - b) % mod;
c = a * b % mod;Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: (frac{8}{2} = 4), но (frac{8 % 5 = 3}{2 % 5 = 2} neq 4).
Нужно найти некоторый элемент, который будет себя вести как (frac{1}{a} = a^{-1}), и вместо «деления» домножать на него. Назовем такой элемент обратным.
Способ 1: бинарное возведение в степень
Если модуль (p) простой, то решением будет (a^{-1} equiv a^{p-2}). Это следует из малой теоремы Ферма:
Теорема. (a^p equiv a pmod p) для всех (a), не делящихся на (p).
Доказательство. (для понимания несущественно, можно пропустить)
[
begin{aligned}
a^p &= (underbrace{1+1+ldots+1+1}_text{$a$ раз})^p
\ &= sum_{x_1+x_2+ldots+x_a = p} P(x_1, x_2, ldots, x_a) & text{(раскладываем по определению)}
\ &= sum_{x_1+x_2+ldots+x_a = p} frac{p!}{x_1! x_2! ldots x_a!} & text{(какие слагаемые не делятся на $p$?)}
\ &equiv P(p, 0, ldots, 0) + ldots + P(0, 0, ldots, p) & text{(все остальные не убьют $p$ в знаменателе)}
\ &= a
end{aligned}
]
Здесь (P(x_1, x_2, ldots, x_n) = frac{k}{prod (x_i!)}) это мультиномиальный коеффициент — количество раз, которое элемент (a_1^{x_1} a_2^{x_2} ldots a_n^{x_n}) появится при раскрытии скобки ((a_1 + a_2 + ldots + a_n)^k).
Теперь два раза «поделим» наш результат на (a).
[ a^p equiv a implies a^{p-1} equiv 1 implies a^{p-2} equiv a^{-1} ]
Получается, что (a^{p-2}) ведет себя как (a^{-1}), что нам по сути и нужно. Посчитать (a^{p-2}) можно за (O(log p)) бинарным возведением в степень.
Приведем код, который позволяет считает (C_n^k).
int t[maxn]; // факториалы, можно предподситать простым циклом
// бинарное возведение в степень
int bp (int a, int n) {
int res = 1;
while (n) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// находит обратный элемент как a^(p-2)
int inv (int x) {
return bp(x, mod-2);
}
int c (int n, int k) {
return t[n] * inv(t[k]) % mod * inv(t[n-k]) % mod;
}Способ 2: диофантово уравнение
Диофантовыми уравнениями называют такие штуки:
[ ax + by = 1 ]
Требуется решить их в целых числах, то есть (a) и (b) известны, и нужно найти такие целые (возможно, отрицательные) (x) и (y), чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.
Подставим в качестве (a) и (b) соответственно (a) и (m)
[ ax + my = 1 ]
Одним из решений уравнения и будет (a^{-1}), потому что если взять уравнение по модулю (m), то получим
[ ax + by = 1 iff ax equiv 1 iff x equiv a^{-1} pmod m ]
Преимущества этого метода над возведением в степень:
- Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
- Алгоритм проще выполнять руками.
Сам автор почти всегда использует возведение в степень.
Почему (10^9+7)?
- Это выражение довольно легко вбивать (
1e9+7). - Простое число.
- Достаточно большое.
intне переполняется при сложении.long longне переполняется при умножении.
Кстати, (10^9 + 9) обладает теми же свойствами. Иногда используют и его.
Предподсчёт обратных факториалов за линейное время
Пусть нам нужно зачем-то посчитать все те же (C_n^k), но для больших (n) и (k), поэтому асимптотика (O(n log m)) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.
Если у нас уже написан inv, то нам не жалко потратить (O(log m)) операций, посчитав (m!^{-1}).
После этого мы будем считать ((m-1)!^{-1}) как (m!^{-1} m = frac{1}{1 cdot 2 cdot ldots cdot (m-1)}).
int f[maxn];
f[0] = 1;
for (int i = 1; i < maxn; i++)
f[i] = i*f[i-1] % mod;
int r[maxn];
r[maxn-1] = inv(f[maxn-1])
for (int i = maxn-1; i >= 1; i--)
r[i-1] = r[i]*i % mod;TODO: техника с сайта емакса.
Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.
Обратный элемент в кольце по модулю
Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .
Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.
Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.
Для того, чтобы показать это, рассмотрим следующее уравнение:
Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:
Таким образом, найденное x и будет являться обратным к a.
Обратный по модулю
❓Инструкция
Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.
Использование:
Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.
Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».
Если установлена галочка «подробнее», то калькулятор помимо обратного элемента по модулю выдает некоторые этапы вычисления.
Ограничения:
Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.
📖 Теория
Что значит по модулю?
Синонимом к данному выражению является выражение «остаток от деления«. То есть выражение «5 по модулю 3» эквивалентно выражению «остаток от деления 5 на 3». И в том и в другом случае подразумевается в ответе число 2, так как остаток от деления 5 на 3 = 2.
Стоить отметить тот факт, что по модулю m мы имеем числа от 0 до m — 1. Действительно, остаток от деления на m никогда не превысит m — 1.
Что такое обратное?
Напомним, что число, умноженное на его обратное, равно 1. Из базовой арифметики мы знаем, что:
Число, обратное к числу A, равно 1 / A, поскольку A * (1 / A) = 1 (например, значение, обратное к 5, равно 1/5). Все действительные числа, кроме 0, имеют обратную Умножение числа на обратное к A эквивалентно делению на A (например, 10/5 соответствует 10 * 1/5)
Что такое обратное по модулю?
В модульной арифметике у нас нет операции деления. Тем не менее, у нас есть модульные инверсии.
Модульная инверсия a (mod m) есть a-1 (a * a-1) ≡ 1 (mod m) или эквивалентно (a * a-1) mod m = 1 Только числа, взаимно простые с модулем m, имеют модульное обратное.
Говоря проще, обратным элементом к a по модулю m является такое число b, что остаток от деления (a * b) на модуль m равно единице (a * a-1) mod m = 1
Как найти модульный обратный
Наивный метод нахождения модульного обратного a ( по модулю m) является:
Шаг 1. Рассчитать a * b mod m для значений b от 0 до m — 1
Шаг 2. Модульная инверсия a mod m — это значение b, при котором a * b mod m = 1
Обратите внимание, что термин b mod m может иметь только целочисленное значение от 0 до m — 1, поэтому тестирование больших значений чем (m-1) для b является излишним.
Вы наверно уже догадались, что наивный метод является очень медленным. Перебор всех чисел от 0 до m-1 для большого модуля довольно-таки трудоемкая задача. Существует гораздо более быстрый метод нахождения инверсии a (mod m). Таковым является расширенный алгоритм Евклида, который реализован в данном калькуляторе.
Расширенный алгоритм Евклида
Представим наибольший общий делитель числа a и модуля m в виде ax + my. То есть НОД(a, m) = ax + my. Помним, что обратный элемент существует только тогда, когда a и m взаимно просты, то есть их НОД(a, m) = 1. Отсюда: ax + my = 1 — линейное диофантово уравнение второго порядка. Необходимо решить данное уравнение в целых числах и найти x, y.
Найденный коэффициент x будет являться обратным элементом к a по модулю m. Это следует оттуда, что, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим: ax = 1 (m).
Расширенный алгоритм Евклида, в отличие от классического, помимо наибольшего общего делителя позволяет найти также коэффициенты x, y.
Алгоритм:
Вход: a, m ≠ 0
Выход: d, x, y, такие что d = gcd(a, m) = ax + my
1. [Инициализация] (a0, a1) := (a, m); (x0, x1) := (1, 0); (y0; y1) := (0, 1).
2. [Основной цикл] Пока a1 ≠ 0 выполнять {q = QUO(a0, a1);
(a0, a1) := (a1, a0 — a1q); (x0, x1) := (x1, x0 — x1q); (y0, y1) := (y1, y0 — y1q);
QUO(a0, a1) — целая часть от деления a0 на a1
3. [Выход] Вернуть (d, x, y) = (a0, x0, y0)
Битовая сложность расширенного алгоритма Евклида равна O((log2(n))2) , где n = max (|a|, |m|)
Непонятен алгоритм? Ничего страшного, примеры ниже именно для этого и предназначены.
➕ Примеры
Пример для наивного метода.
Пусть a = 3, m = 7. То есть нам необходимо найти обратный элемент к 3 по модулю 7.
Шаг 1. Рассчитать a * b mod m для значений B от 0 до m-1. По очереди проверяем числа от 0 до 6.
3 * 0 ≡ 0 (mod 7) — не подходит
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <—— Обратное найдено.
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
при b = 5 выполнилось условие, что a * b ≡ 1 (m). Следовательно, b = 5 является обратным элементом к 3 по модулю 7.
Пример на расширенный алгоритм Евклида.
Пусть аналогично предыдущему примеру имеем a = 3, m = 7. Также, требуется найти обратный элемент к 3 по модулю 7. Согласно алгоритму начинаем заполнять таблицу на каждом этапе цикла.
| Итерация | q | a0 | a1 | x0 | x1 | y0 | y1 |
| 0 | — | 3 | 7 | 1 | 0 | 0 | 1 |
| 1 | 0 | 7 | 3 | 0 | 1 | 1 | 0 |
| 2 | 2 | 3 | 1 | 1 | -2 | 0 | 1 |
| 3 | 3 | 1 | 0 | -2 | 0 | 1 | -3 |
После 3-ей итерации получили a1 = 0, строго по алгоритму из раздела «Теория» заканчиваем работу алгоритма.
(d, x, y) = (a0, x0, y0)
(d, x, y) = (1, -2, 1), видим, что d = НОД(3, 7) = 1, следовательно числа 3 и 7 являются взаимно простыми, а значит обратный существует.
Делаем проверку:
3 * (-2) + 7 * 1 = 1
-6 + 7 = 1
1 = 1 — верно!
Обратным элементом к тройке по модулю 7 является x = -2. По модулю 7 число -2 равно 5. Получили, что x = 5 является обратным элементом к 3 по модулю 7.
There are many methods available, e.g. the extended Euclidean algorithm, $ $ or a special case of Euclid’s algorithm that computes inverses modulo primes that I call Gauss’s algorithm. $ $
The calculations are usually simpler using modular fraction arithmetic e.g. see here, and here and here for circa $20$ motley worked examples via a handful of methods (and see the sidebar «Linked» questions lists there for many more).
Update $ $ March $16, 2020!:,$ for completeness we apply some of the linked methods below.
$!!bmod 31!:, dfrac{1}{7}equiv dfrac{4}{28}equivdfrac{-27}{-3}equiv 9 $ by Gauss’s algorithm.
$!!bmod 31!:, dfrac{1}{7}equiv dfrac{1}{-6},dfrac{1}{4}equiv dfrac{-30}{-6},dfrac{32}{4}equiv 5cdot 8equiv 9$
As here: $ $ the freedom to choose $rmcolor{#c00}{even}$ residue reps $!bmod!$ odds makes division by 2 easy:
$!!bmod 31!:, dfrac{1}{7}equivdfrac{color{#c00}{32}}{color{#c00}{-24}}equivdfrac{4}{-3}equivdfrac{-27}{-3}equiv 9$
By the fractional extended Euclidean algorithm, or associated equational form
$ begin{align} bmod 31!: dfrac{0}{31}overset{largefrown}equivcolor{#c00}{dfrac{1}7} , &!!!overset{largefrown}equivcolor{#0a0}{dfrac{-4}3}overset{largefrown}equivcolor{#90f}{dfrac{9}1}\[.7em]
text{said equationally}
[![1]!] 31, x&,equiv 0 \
[![2]!] color{#c00}{7,x}& color{#c00}{ equiv 1}!!!\
[![1]!]-4,[![2]!] rightarrow [![3]!] color{#0a0}{3,x} & color{#0a0}{equiv {-}4} \
[![2]!] — 2,[![3]!] rightarrow [![4]!], color{#90f}{x}& color{#90f}{ equiv 9}
end{align}$
Below we explain the basic idea behind the method of Inverse Reciprocity.
$!!bmod 31!:, n equiv dfrac{1}7equiv dfrac{1+31color{#c00}k}7. $ For an exact quotient we seek $,k,$ with $,7mid 1!+!31k,,$ i.e.
$!!bmod 7!:, begin{align}0&equiv 1!+!31k\ &equiv 1 + 3kend{align}!$ $iff! begin{align}3k&equiv-1\ &equiv, 6end{align}!$ $iff color{#c00}{kequiv 2}, $ so $ n equiv dfrac{1!+!31(color{#c00}2)}7equiv 9pmod{!31}$
Or $ $ by Euler $rm (a,m)=1 Rightarrow a^{-1} equiv a^{phi(m)-1}pmod{! m},,$ quickly computable by repeated squaring.
Remark $ $ The latter yields a simple closed form for CRT (Chinese Remainder Theorem)
$quad$ if $rm, (m,n)=1, $ then $rmquad begin{eqnarray}rm x!&equiv&rm a (mod m)\ rm x!&equiv&rm b (mod n)end{eqnarray} iff xequiv a,n^{phi(m)}!+b,m^{phi(n)} (mod mn)$
More generally see the Peirce decomposition.