요약

소수 $p$에 대해 $a^{p-2} = a^{-1} \pmod{p}$이다. 일반화하면 모든 $n$에 대해 $a^{\phi(n)-1} = a^{-1} \pmod{n}$이다.

위수란?

어떤 수 $a$와 $n$에 대해

\[a^x = 1 \pmod{n}\]

를 만족하는 자연수 $x$의 최솟값을 법 $n$에서의 $a$의 위수(order)라고 하고, 일반적으로 ${\rm ord}_n(a)$와 같이 표기한다.

$2^4 = 1 \pmod{5}$이므로 법 5에서의 2의 위수 ${\rm ord}_5(2) = 4$이다.

위수의 존재성

위수가 존재하는 필요충분조건은 $a$와 $n$이 서로소, 즉 ${\rm gcd}(a, n) = 1$이라는 것이 알려져 있다.

페르마의 소정리 (Fermat’s little Theorem; FlT)

소수 $p$에 대해 $a^{p} = a \pmod{p}$이다.

이때 $p \nmid a$이면 $a^{p-1} = 1 \pmod{p}$이다. 하지만 이것이 위수가 $p-1$임을 보장하지는 않는데, 위수의 성질을 이용하면 위수가 $p-1$의 약수임을 알 수 있다.

오일러 피 함수 (Euler’s totient function)

오일러 피 함수는 다음과 같이 정의된다.

\[\phi : \mathbb{N} \to \mathbb{N}\] \[\phi(n) = \left| \left\{ x < n \mid {\rm gcd}(n, x) = 1 \right\} \right|\]

$n$보다 작은 자연수 중 $n$과 서로소인 것의 개수와 같다.

이 함수는 다음과 같은 성질을 지닌다.

서로소인 두 수 $m$과 $n$에 대해 $\phi(mn) = \phi(m)\phi(n)$이다.

소수 $p$와 자연수 $k$에 대해 $\phi(p^k) = p^{k-1}(p-1)$이다.

따라서 다음을 얻을 수 있다.

\[\phi(n) = n \prod_{p \mid n}{\left(1 - \frac{1}{p}\right)}\]

오일러의 정리 (Euler’s theorem)

서로소인 두 수 $a$와 $n$에 대해 $a^{\phi(n)} = 1 \pmod{n}$이다.

페르마 소정리를 일반화한 것이다. (소수 $p$에 대해 $\phi(p)=p-1$이므로 $a^{\phi(p)} = a^{p-1} = 1 \pmod{p}$)

이 역시 위수가 $\phi(n)$임을 보장하지는 않는다.

모듈러 역원이란?

어떤 수 $a$와 $n$에 대해

\[ax = 1 \pmod{n}\]

를 만족하는 자연수 $x$를 법 $n$에서의 $a$의 모듈러 역원이라고 하고, 일반적으로 $a^{-1}$으로 표기한다.

모듈러 역원의 존재성

식을 변형하면 정수 $m$에 대해 다음을 얻는다.

\[ax - mn = 1\]

위 식은 $x$와 $m$에 대한 일차식으로, 정수 해가 존재할 필요충분조건은 ${\rm gcd}(a, n) = 1$이다.

오일러 정리를 이용한 모듈러 역원

모듈러 역원이 존재한다면 ${\rm gcd}(a, n) = 1$이므로, 오일러 정리를 이용하면 $a^{\phi(n)} = 1 \pmod{n}$이다. 따라서 모듈러 역원은 $a^{\phi(n)-1}$이다.

$\phi(n)$을 구하는 것은 소인수 분해를 하는 것과 동치이므로, 오일러 체를 이용하면 $O(n)$의 전처리를 거치면 $O(\log{n})$에 처리할 수 있다.

백준 13174 - 괄호와 같이 법 $n$이 주어지면 $\phi(n)$을 미리 계산하여 상수로 지정하고 쓸 수 있다.

많은 경우 법으로 소수 $p$가 주어지는데, 페르마의 소정리 또는 $\phi(p) = p - 1$를 이용하면 모듈러 역원을 쉽게 계산할 수 있다.