큰 거듭제곱의 나머지를 빠르게 계산하는 강력한 도구이다. 페르마의 소정리는 소수에 대한 성질이고, 오일러는 이를 모든 법으로 일반화했다. RSA 암호가 작동하는 이유가 바로 이 정리이다.
핵심 개념
- 오일러 함수 $\varphi(n)$: $1$부터 $n$까지의 수 중 $n$과 서로소인 수의 개수. $\varphi(p)=p-1$, $\varphi(p^k)=p^k-p^{k-1}$, 서로소인 $m,n$에 대해 $\varphi(mn)=\varphi(m)\varphi(n)$
핵심 정리
- 페르마의 소정리: $p$가 소수이고 $p\nmid a$이면 $a^{p-1}\equiv1\pmod p$
- 오일러 정리: $\gcd(a,n)=1$이면 $a^{\varphi(n)}\equiv1\pmod n$
증명 보기
아이디어. $n$과 서로소인 수들을 모두 $a$배 해도, 법 $n$으로 보면 같은 수들이 순서만 바뀌어 나타난다. 그래서 두 곱이 같아진다.
$n$과 서로소인 $1$ 이상 $n$ 이하의 수를 $r_1,r_2,\dots,r_k$ ($k=\varphi(n)$)라 하자. 이제 $ar_1,ar_2,\dots,ar_k$를 생각하자.
- 각 $ar_i$는 $n$과 서로소이다($a$와 $r_i$가 모두 서로소이므로).
- 이들은 법 $n$으로 서로 다르다. $ar_i\equiv ar_j$이면 $\gcd(a,n)=1$이므로 $a$를 소거하여 $r_i\equiv r_j$, 즉 $i=j$이다.
따라서 $ar_1,\dots,ar_k$를 $n$으로 나눈 나머지는 $r_1,\dots,r_k$를 순서만 바꾼 것이다. 모두 곱하면
$$a^k\,r_1r_2\cdots r_k\equiv r_1r_2\cdots r_k\pmod n$$
이다. $r_1\cdots r_k$는 $n$과 서로소이므로 양변에서 소거하면 $a^k\equiv1$, 즉 $a^{\varphi(n)}\equiv1\pmod n$이다. $n=p$가 소수이면 $\varphi(p)=p-1$이므로 페르마의 소정리가 된다. $\blacksquare$
예제
- $3^{100}\bmod7$: $3^6\equiv1$이고 $100=6\cdot16+4$이므로 $3^{100}\equiv3^4=81\equiv4$
- $\varphi(12)$: $12$와 서로소인 수는 $1,5,7,11$이므로 $4$. 공식으로는 $\varphi(4)\varphi(3)=2\cdot2=4$
- $7^{222}$의 일의 자리: $\varphi(10)=4$이고 $222=4\cdot55+2$이므로 $7^{222}\equiv7^2=49\equiv9$
확인 문제
$2^{2026}$을 $13$으로 나눈 나머지를 구하시오.
풀이 보기
페르마의 소정리에 의해 $2^{12}\equiv1\pmod{13}$이다. $2026=12\cdot168+10$이므로 $2^{2026}\equiv2^{10}=1024$이다. $1024=13\cdot78+10$이므로 나머지는 $10$이다.
정리
- $a^{p-1}\equiv1\pmod p$, $a^{\varphi(n)}\equiv1\pmod n$
- 거듭제곱의 나머지는 지수를 $\varphi(n)$으로 나눈 나머지로 줄인다.
