페르마의 소정리
페르마의 소정리는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다.
p가 소수이고, a가 정수 일 때, 페르마의 소정리에 따르면,
$$a^{p} \equiv a \pmod{p}$$
임의의 정수 a의 p승을 p로 나눈 나머지는 a를 p로 나눈 나머지와 같다.
합동식을 이용한 증명
먼저 a가 p의 배수라면 좌변과 우변 모두 나머지가 0이므로 성립함을 알 수 있다.
이제 a가 p의 배수가 아니라면 a, 2a, 3a, ..., (p-1)a를 p로 나눈 나머지는 모두 다르다.
이는 귀류법으로 증명이 가능한데, 1< i, j < p-1 사이에 p로 나누었을 때, 나머지가 같은 i, j 가 존재한다고 가정해 보자
그러면 a(i-j) 를 p로 나눈 나머지는 0이 되므로 a(i-j)는 p의 배수가 된다.
하지만, a는 p의 배수가 아니라고 가정 했으므로, 나머지가 같은 i와 j는 존재하지 않음을 알 수 있다.
이를 이용하면
\begin{align*}
&a \cdot 2a \cdot 3a \cdot \ldots \cdot (p-1)a \cdot (p-1)!^{-1} \equiv 1 \times 2 \times 3 \times \ldots \times (p-1) \ (\text{mod}\ p) \\\\
&a^{p-1} \cdot (p-1)!^{-1} \equiv (p-1)! \ (\text{mod}\ p) \\\\
&a^{p-1} \equiv 1 \ (\text{mod}\ p) \\\\
&a^p \equiv a \ (\text{mod}\ p)
\end{align*}
위와 같은 식을 얻을 수 있다.