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

Обратный элемент в кольце по модулю

Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.

Обратный элемент в кольце по модулю

Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .

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

Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.

Для того, чтобы показать это, рассмотрим следующее уравнение:

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

Как вычислить обратный элемент по модулю [дубликат]

В общем случае ответ @MBo про расширенный алгоритм Евклида работает в большом классе колец, так называемых Евклидовых кольцах. Например, в кольцах многочленов над полями.

Но в частном случае циклических групп, когда известно разложение порядка группы на множители, можно пользоваться теоремой Эйлера. В вашем случае 4^10 == 1 (mod 11) , следовательно 4^(-1) == 4^9 (mod 11) == 3 (mod 11) .

Чуть более обще. Пусть n — модуль, phi(n) — функция Эйлера для n , тогда a^(-1) == a^(phi(n)-1) (mod n) .

Обратный элемент по модулю

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего \(10^9 + 7\) ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.

Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: \(\frac<8> <2>= 4\) , но \(\frac<8 \% 5 = 3> <2 \% 5 = 2>\neq 4\) .

Способ 1: бинарное возведение в степень

Если модуль \(p\) простой, то решением будет \(a^ <-1>\equiv a^\) . Это следует из малой теоремы Ферма:

Теорема. \(a^p \equiv a \pmod p\) для всех \(a\) , не делящихся на \(p\) .

Доказательство. (для понимания несущественно, можно пропустить)

Здесь \(P(x_1, x_2, \ldots, x_n) = \frac<\prod (x_i!)>\) это мультиномиальный коеффициент — количество раз, которое элемент \(a_1^ a_2^ \ldots a_n^\) появится при раскрытии скобки \((a_1 + a_2 + \ldots + a_n)^k\) .

Теперь два раза «поделим» наш результат на \(a\) .

\[ a^p \equiv a \implies a^ \equiv 1 \implies a^ \equiv a^ <-1>\]

Получается, что \(a^\) ведет себя как \(a^<-1>\) , что нам по сути и нужно. Посчитать \(a^\) можно за \(O(\log p)\) бинарным возведением в степень.

Приведем код, который позволяет считает \(C_n^k\) .

Способ 2: диофантово уравнение

Диофантовыми уравнениями называют такие штуки:

Требуется решить их в целых числах, то есть \(a\) и \(b\) известны, и нужно найти такие целые (возможно, отрицательные) \(x\) и \(y\) , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.

Подставим в качестве \(a\) и \(b\) соответственно \(a\) и \(m\)

Одним из решений уравнения и будет \(a^<-1>\) , потому что если взять уравнение по модулю \(m\) , то получим

\[ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ <-1>\pmod m \]

Преимущества этого метода над возведением в степень:

• Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
• Алгоритм проще выполнять руками.

Сам автор почти всегда использует возведение в степень.

Почему \(10^9+7\) ?

1. Это выражение довольно легко вбивать ( 1e9+7 ).
2. Простое число.
3. Достаточно большое.
4. int не переполняется при сложении.
5. long long не переполняется при умножении.

Кстати, \(10^9 + 9\) обладает теми же свойствами. Иногда используют и его.

Предподсчёт обратных факториалов за линейное время

Пусть нам нужно зачем-то посчитать все те же \(C_n^k\) , но для больших \(n\) и \(k\) , поэтому асимптотика \(O(n \log m)\) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.

Если у нас уже написан inv , то нам не жалко потратить \(O(\log m)\) операций, посчитав \(m!^<-1>\) .

Обратный по модулю в кольце

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

Использование:

Заполняются два поля — число 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.

Алгоритм:

Выход : d, x, y, такие что d = gcd(a, m) = ax + my

3. [Выход] Вернуть (d, x, y) = (a₀, x₀, y₀)

Битовая сложность расширенного алгоритма Евклида равна O((log₂(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) = (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.

Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.