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

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

  • автор:

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

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

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

Рассчитать
Обратный элемент
Ссылка Сохранить Виджет

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

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

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

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

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

Таким образом, найденное x и будет являться обратным к a.

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

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

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

 c = (a + b) % mod; c = (mod + a - b) % mod; c = a * b % mod;

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

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

Если модуль \(p\) простой, то решением будет \(a^ \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^ \]

Получается, что \(a^\) ведет себя как \(a^\) , что нам по сути и нужно. Посчитать \(a^\) можно за \(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: диофантово уравнение

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

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

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

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

\[ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ \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!^\) .

 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: техника с сайта емакса.

Обратное число к а по модулю m

Обратное число Даны два целых числа m и a. Если не существует обратного числа к a по модулю m, то выведите число −1, а если существует, то выведите это число (ответ должен лежать в границах от 0 до m−1). Входные данные В единственной строке входных данных даны два целых числа 1 Выходные данные Выведите ответ на задачу. Примеры Ввод 179 57 Вывод 22

b = 0 a = list(map(int, input().split())) b = pow(a[1], a[0] - 2, a[0]) if pow(a[1], a[0] - 2, a[0]) == 0: print(-1) else: print(b) 

Отслеживать

32.4k 3 3 золотых знака 20 20 серебряных знаков 56 56 бронзовых знаков

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

Фактическая польза от обратного по модулю в том, что он заменяет деление. А именно, если нам в рамках вычислений хочется найти значение $\frac \pmod

$, то мы считаем это значение эквивалентным значению $A \cdot B^ \pmod

$.

Чтобы найти обратное по модулю, есть несколько разных техник, но самая популярная — теорема Эйлера:

Теорема Эйлера

Или это же выражение для простого модуля $p$ называется малой теоремой Ферма:

Малую теорему Ферма можно достаточно просто доказать комбинаторно. Поставим другую задачу — подсчет числа способов раскрасить $p$-угольник в $a$ цветов. Раскрасим каждую вершину в какой-то цвет. Всего таких раскрасок $a^p$. Заметим, что поскольку $p$ простое, то у всех раскрасок, кроме тех, где все раскрашено в один цвет поворотом получается ровно $p$ раскрасок. Значит всего различных раскрасок $\frac

+ a$. Это число должно быть целым, а значит $a^p — a$ делится на $p$, откуда $a^

— 1 \equiv 0 \pmod

$.

Как теперь научиться делить? Все просто:

Значит, для простых $p$ достаточно посчитать $a^$ с помощью быстрого возведения в степень

Диофантово уравнение

Альтернативный вариант — свести уравнение $ax \equiv 1 \pmod

$ к диофантову уравнению $$ ax + py = 1$$

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *