모듈러 곱셈 역원 (Modular Multiplicative Inverse) 의 정의는 다음과 같습니다.
$$ ax \equiv 1 \pmod{n} $$ 이면 $x$를 법 $n$에서의 $a$에 대한 모듈러 곱셈 역원이라 하고, $$ x \equiv a^{-1} \pmod{n} $$ 로 표현한다.$x$가 존재할 조건은 $a$와 $n$이 서로소 인 것입니다.
1. $a$와 $n$이 서로소가 아니면 역원이 존재하지 않는 것 보이기
$a$와 $n$이 서로소가 아니라 하면 $g > 1$인 어떤 정수 $g$와 정수 $p$, $q$에 대해 $gp = a$, $gq = n$이라 할 수 있다.
$ax \equiv 1 \pmod{n}$에서 어떤 정수 $k$에 대하여 $ax - 1 = kn$이고, $gp = a$, $gq = n$에서 $gpx - 1 = kgq$이다.
식 정리를 해주면 $(px - kq)g = 1$인데, $(px - kq)$가 정수끼리의 덧뺄셈, 곱셈으로만 이루어져있으니 똑같이 정수이다.
따라서 $(px - kq) = -1$, $g = - 1$이거나, $(px - kq) = 1$, $g = 1$여야 하는데, 이는 $g > 1$이란 것에 모순이다. 따라서 역원이 존재하면 $a$, $n$은 서로소이다.
("역원이 존재하면 $a$, $n$은 서로소"와 "$a$와 $n$이 서로소가 아니면 역원이 존재하지 않음"은 대우관계)
2. $a$와 $n$이 서로소이면 역원이 존재하는 것 보이기
오일러의 정리 에 의해 $a^{\phi(n)} \equiv 1 \pmod{n}$이다.
따라서 $$ x \equiv a^{\phi(n) - 1} \equiv a^{-1} \pmod{n} $$ 이다.