증명의 스케치
굉장히 중요하게 쓰일 모듈러 연산 성질 로, $ab \equiv ac \pmod{p}$이고, $a$와 소수 $p$가 서로소이면 $b \equiv c \pmod{p}$ 라는 성질이 있음.
$1$부터 $p - 1$까지의 수가 있는 집합 $S_{1} = \{ 1, 2, \cdots , p - 2, p - 1 \}$의 원소 각각에다가 $a$를 곱하면 $S_{2} = \{ 1a, 2a, \cdots , (p - 2)a, (p - 1)a \}$ 꼴이 된다.
만약 $ax \equiv ay \pmod{p}$이면 위의 성질에서 $x \equiv y \pmod{p}$여야만 하는데, 집합 $S_{1}$에서 $p$로 나누었을 때의 나머지가 서로 같은 원소가 없었으므로 $S_{2}$의 원소를 $p$로 나눈 나머지들도 나머지가 같을 수가 없다.
따라서 $S_{3} = \{ 1a \pmod{p}, 2a \pmod{p}, \cdots , (p - 2)a \pmod{p}, (p - 1)a \pmod{p} \}$라 하고, 이를 정렬하면 $1$부터 $p - 1$까지의 원소가 모두 한 번씩 나오게 된다. 이는 집합 $S_{1}$과 완전히 같다.
$S_{1} = S_{3}$이므로 $S_{1}$에 있는 원소들의 곱과 $S_{3}$에 있는 원소들의 곱이 같다는걸 알 수 있다.
+) $1$부터 $p - 1$까지는 정수가 $p - 1$개 있다. ($1$부터 $3$까지의 정수가 $3$개인 것처럼)
$S_{1}$ 부분의 곱은 $\prod\limits_{k = 1}^{p - 1} k \pmod{p}$로 쓸 수 있고, $S_{3}$ 부분의 곱은 $\prod\limits_{k = 1}^{p - 1} ka \equiv a^{p - 1} \prod\limits_{k = 1}^{p - 1} k \pmod{p}$로 쓸 수 있다.
(합동식이 아니어도 $\prod\limits_{k = 1}^{p - 1} ka = a^{p - 1} \prod\limits_{k = 1}^{p - 1} k$은 성립한다.)
$S_{1}$의 곱과 $S_{3}$의 곱이 같으므로 $\prod\limits_{k = 1}^{p - 1} k \equiv a^{p - 1} \prod\limits_{k = 1}^{p - 1} k \pmod{p}$이라 할 수 있고, $1$부터 $p - 1$까지 모두 $p$와 서로소이므로 (서로소가 아니라면 그건 $p$가 애초에 소수가 아니다.) $1$부터 $p - 1$까지의 곱 또한 $p$와 서로소이다.
따라서 $K = \prod\limits_{k = 1}^{p - 1} k$라 하면 $K \equiv a^{p - 1} K \pmod{p}$이고, $K$가 $p$와 서로소이므로 $1 \equiv a^{p - 1} \pmod{p}$이다.