페르마의 소정리 (Fermat’s Little Theorem)

페르마의 소정리) 소수 $p$와 정수 $a$에 대해
\[ a^p \equiv a \pmod p \]

아주 간단하지만 강력한 정리입니다. 보통 문제에서 어떤 수의 거듭제곱을 다른 어떤 수로 나눈 나머지를 구하는 과정이 있는데 나누는 수가 소수라면 써봄직합니다.

만약 $a$가 $p$의 배수가 아니라면 아래 보조정리를 써서 $a^{p-1} \equiv 1 \pmod p$라고도 쓸 수 있습니다.

보조정리) 정수 $a$, $b$, $x$, $m$에 대해 $m$과 $x$가 서로소이면
\[ ax \equiv bx \pmod m \qquad \Rightarrow \qquad a \equiv b \pmod m \] 증명) 합동식의 정의에서 $ax-bx = (a-b)x$는 $m$의 배수입니다. 그런데 $x$가 $m$과 서로소이므로 $(a-b)$가 $m$의 배수가 될 수 밖에 없습니다. ■

증명 1) 합동식의 성질에 의해, $a=0, 1, 2, \cdots, p-1$에 대해서만 성립함을 보여도 충분합니다. 수학적 귀납법을 씁시다. 먼저 $a=0$일 때 자명하게 성립합니다. $a=k$일 때 성립한다고 가정하면 ($k \ge 0$) $k^p \equiv k \pmod p$이고,

\[ (k+1)^p = \sum_{i=0}^p \binom{p}{i} k^i \]

그런데 이항계수의 정의에서

\[ \binom{p}{i} = \frac{p!}{i!(p-i)!} = \frac{p(p-1)\cdots(p-i+1)}{i(i-1)\cdots(2)(1)} \]

는 $1 \le i \le p$일 때 $p$의 배수이고 ($p$가 소수여서 분모에도 $p$가 있어야 분자에 있는 $p$와 약분이 됨), $i=0$ 또는 $i=p$이면 1입니다. 그러므로

\[ (k+1)^p \equiv \sum_{i=0}^p \binom{p}{i} k^i \equiv k^p + 1 \equiv k + 1 \pmod p \]

따라서 모든 정수 $a \ge 0$에 대해 성립합니다. ■

증명 2) $a$가 $p$의 배수가 아니라고 가정하고 변형된 형태를 증명하겠습니다. 만약 $m$과 $n$이 $0$보다 크고 $p$보다 작은, 서로 다른 정수인 경우

\[ m \not\equiv n \pmod p \qquad \Rightarrow \qquad ma \not\equiv na \pmod p \]

가 위 보조정리에 의해 성립합니다. $m$과 $n$을 $p$로 나눈 나머지는 서로 다르고 $a$가 $p$와 서로소이기 때문이죠. 즉, $a, 2a, 3a, \cdots, (p-1)a$를 $p$로 나눈 나머지는 모두 달라야 합니다. 여기서 이 $p-1$개의 수들은 모두 $p$의 배수가 아니기 때문에 나머지가 0이 될 수는 없습니다. 따라서 이 수들을 $p$로 나눈 나머지를 모으면 $1,2,3,\cdots,p-1$이 됩니다. 그러므로

\[ a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod p \]

또는

\[ (p-1)! a^{p-1} \equiv (p-1)! \pmod p \]

그런데 $(p-1)!$은 $p$와 서로소이므로 보조정리에 의해

\[ a^{p-1} \equiv 1 \pmod p \]

가 성립합니다. ■