소수 $p$와 정수 $a$에 대해
\[ a^p \equiv a \pmod p \]
합동식의 성질에 따라 $a=0,1,2,\cdots,p-1$에 대해 성립함을 보여도 충분합니다.
수학적 귀납법을 씁시다. 먼저 $a=0$일 때 자명하게 성립합니다. 그리고 $a=k$일 때
성립한다고 가정합시다.
\[ k^p \equiv k \pmod p \]
$a=k+1$일 때 성립함을 증명하려면 이항정리를 사용해야 합니다.
\[ (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 1} \]
은 $1 \le i \le p$일 때 $p$의 배수이고 $i$가 0 또는 $p$이면 1입니다. 따라서
\[ (k+1)^p = \sum_{i=0}^p \binom p i k^i \equiv
\binom p 0 k^0 + \binom p p k^p = k^p + 1 \equiv k + 1 \pmod p \]
$a=k+1$일 때에도 성립하므로 증명 끝.
아주 간단하지만 강력한 정리입니다. 어떤 수의 거듭제곱을 다른 어떤 수로 나눈 나머지를 구해야 하는데 나누는 수가 소수라면 써봄직합니다.
만약 $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$의 배수입니다. 그런데 $m$과 $x$가
서로소이므로 $a-b$는 반드시 $m$의 배수입니다.