Modular Inverse with Fermat's little Theorem

알고리즘 문제를 풀다 보면 분수 형태의 값을 모듈러 연산 아래에서 계산해야 하는 경우가 자주 등장한다. 하지만 모듈러 연산에서는 일반적인 나눗셈을 그대로 사용할 수 없다.

따라서 어떤 수 $b$로 나누는 대신, $b$의 모듈러 역원 $b^{-1}$을 곱하는 방식으로 계산한다.

즉,

$$
\frac{a}{b} \pmod m
$$

를 직접 계산하는 대신,

$$
a \times b^{-1} \pmod m
$$

의 형태로 바꾸어 계산하는 것이다.

모듈러 역원이란?

어떤 정수 $a$에 대하여,

$$
a \times x \equiv 1 \pmod m
$$

을 만족하는 정수 $x$를 $a$의 모듈러 역원이라고 한다.

예를 들어, $\pmod 7$에서 $3$의 모듈러 역원은 $5$이다.

$$
3 \cdot 5 = 15 \equiv 1 \pmod 7
$$

---

모듈러 합동

모듈러 역원을 이해하려면 먼저 모듈러 합동의 성질을 알아야 한다.

정수 $a, b$에 대하여

$$
a \equiv b \pmod m
$$

이라면, 이는 $a$와 $b$를 $m$으로 나누었을 때 나머지가 같다는 뜻이다.

$$
15 \equiv 1 \pmod 7
$$

실제로 $15$를 $7$로 나눈 나머지도 $1$이고, $1$을 $7$로 나눈 나머지도 $1$이다.

모듈러 합동의 성질

만약

$$
a \equiv b \pmod m,\quad x \equiv y \pmod m
$$

이라면 다음도 성립한다.

1. 덧셈

   $$
   a + x \equiv b + y \pmod m
   $$

2. 뺄셈

   $$
   a - x \equiv b - y \pmod m
   $$

3. 곱셈

   $$
   ax \equiv by \pmod m
   $$

4. 거듭제곱

   $$
   a^n \equiv b^n \pmod m
   $$

이 성질들을 이용하면 복잡한 식도 모듈러 아래에서 안전하게 변형할 수 있다.

---

모듈러 역원이 항상 존재할까?

항상 존재하는 것은 아니다.

정수 $a$의 모듈러 역원이 $\pmod m$에서 존재하려면

$$
\gcd(a, m) = 1
$$

이어야 한다.

즉, $a$와 $m$이 서로소여야 한다.

예를 들어, $\pmod 6$에서 $2$의 역원을 찾아보자.

$$
2x \equiv 1 \pmod 6
$$

을 만족하는 정수 $x$는 존재하지 않는다.

왜냐하면 $2x$는 항상 짝수이므로, 나머지가 $1$이 될 수 없기 때문이다.

---

페르마의 소정리

모듈러 역원을 실제로 계산할 때 가장 자주 사용하는 정리가 바로 페르마의 소정리이다.

$p$가 소수일 때, 임의의 정수 $a$에 대해

$$
a^p \equiv a \pmod p
$$

가 성립한다.

특히 $a$와 $p$가 서로소라면 ($a$가 $p$의 배수가 아닐 때)

$$
a^{p-1} \equiv 1 \pmod p
$$

이 성립한다.

이 식을 보면,

$$
a \cdot a^{p-2} \equiv 1 \pmod p
$$

이므로 $a^{p-2}$는 $a$의 모듈러 역원이 된다.

즉,

$$
a^{-1} \equiv a^{p-2} \pmod p
$$

이다.

---

실전 적용

이제 분수 형태의 값을 모듈러 아래에서 계산할 수 있다.

예를 들어,

$$
\frac{a}{b} \pmod p
$$

를 구하고 싶다면, 이를

$$
a \cdot b^{-1} \pmod p
$$

로 바꾼다.

그리고 $p$가 소수라면, 페르마의 소정리에 의해

$$
b^{-1} \equiv b^{p-2} \pmod p
$$

이므로 최종적으로

$$
\frac{a}{b}
\equiv
a \cdot b^{p-2}
\pmod p
$$

로 계산할 수 있다.

실전 문제에서는 $10^9 + 7$ 등의 큰 소수가 자주 등장하므로, 분할 정복을 이용한 거듭 제곱을 사용해서 모듈러 역원을 구할 수 있다.