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

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

В общем случае ответ @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) .

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

\[ a^p \equiv a \implies a^

\equiv 1 \implies a^

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

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

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

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

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

Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.

Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».

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

Ограничения:

Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.

Что значит по модулю?

Что такое обратное?

Число, обратное к числу 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, имеют модульное обратное.

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

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего \(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 называется такое число b, что:
,
Обратный элемент обозначают как .

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

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

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

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