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

Целое число $x$ будет обратным числу $a$ по модулю $n$, если выполняется тождество

$a·x ≡ 1 \pmod n$,

при этом числа $a$ и $n$ должны быть взаимно простыми. Это значит, что $a$ не делится на $n$. Соответственно единственный их общий делитель (он же наибольший) - это 1.

$gcd(a, n) = 1$

Для расчета обратного числа по модулю применяется расширенный алгоритм Евклида и соотношение Безу.

Соотношение Безу говорит, что существуют такие целые числа $s$, $t$, которые удовлетворяют следующему выражению:

$gcd(a, b) = a·s + b·t$

Для нашего случая:

$gcd(a, n) = a·s + n·t = 1$

Если взять левую и правую часть по модулю $n$, то

$a·s + n·t ≡ 1 \pmod n$

$a·s ≡ 1 \pmod n$, т.к. $n·t ≡ 0 \pmod n$

Чтобы найти наше обратное, нам нужно вычислить коэффициент $s$ в соотношении Безу.

Иногда $s$ получается отрицательным, можем взять его положительный модуль по $n$ без ущерба для исходного уравнения.