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

Нахождение обратного элемента в кольце вычетов

Простой модуль

Начнем с базового случая - когда модуль простой. Рассмотрим два способа:

1. С помощью МТФ. Заметим, что если $p$ - простой модуль, то $a^{p-1}\equiv 1 \mod p$, если $a$ не делится на $p$. Тогда для $a$ обратным элементом будет $a^{p-2}$.
2. С помощью расширенного алгоритма Евклида. Пусть $x$ - искомый обратный элемент. Тогда $ax = 1 - yp$, где $y$ - какое-то целое число. Перепишем это равенство: $ax + yp = 1$. Если $a$ имеет с $p$ общий делитель, отличный от единицы, то оно делится на $p$, этот случай отсеивается проверкой. Теперь считаем, что $(a, p) = 1$. Расширенный алгоритм Евклида, примененный к паре $a, p$, как раз находит такие $x, y$, что $ax + yp = (a, p) = 1$. Тогда решение сводится к запуску расширенного алгоритма Евклида и возвращению одного из найденных коэффициентов.

Составной модуль

TODO.

---

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

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