월슨의 정리

윌슨의 정리 (Wilson's Theorem) 는 정수론의 주요 정리중 하나로, 내용은 다음과 같습니다.

1. $(n - 1)! \equiv -1 \pmod{n}$ 이다.
2. $n$ 이 소수 이다.

두 명제는 동치이다.
$n!$ 은 팩토리얼 입니다.
여기서 두 명제가 동치라는 것은, 완전히 동일하다는 것으로, 1번 문장을 만족하면 2번 문장도 만족하고, 2번 문장을 만족하면 1번 문장도 만족한다는 뜻입니다.
일반적으로 소수 관련 명제가
"$n$이 소수이면 명제 A를 만족한다. (단, 소수가 아니어도 명제 A를 만족할 수도...)"가 되거나
"명제 B를 만족하면 $n$은 소수이다. (단, 모든 소수가 명제 B를 만족시키지는 않...)" 같은 약간의 아쉬움이 있는것과는 대조적입니다.
예를 들어 페르마의 소정리 에서는 $n$이 소수이면 $n$과 서로소인 $a$에 대하여 $a^{n - 1} \equiv 1 \pmod{n}$ 이지만, $a^{n - 1} \equiv 1 \pmod{n}$이라고 꼭 $n$이 소수가 되진 않는 카마이클 수 라는 예외가 있습니다.
또, 윌슨의 정리는 팩토리얼 과 소수의 관계였다면, 볼첸홈의 정리 는 이항계수 와 소수의 관계입니다.
윌슨의 정리는 예외없이 필요충분조건이다보니 정수론의 각종 분야에서 쓰입니다.
윌슨의 정리 증명 1

(증명의 스케치)
$p = 2$, $p = 3$은 직접 손으로 풀어본다.

보조정리
소수 $p$에 대하여 $x^{2} \equiv 1 \pmod{p}$이면 $x \equiv 1 \pmod{p}$이거나 $x \equiv -1 \pmod{p}$이다.
보조정리 증명

증명은 유클리드의 보조정리 에 의해 쉽게 할 수 있습니다.

유클리드의 보조정리
소수 $p$에 대하여 $ab \equiv 0 \pmod{p}$이면 $a \equiv 0 \pmod{p}$이거나 $b \equiv 0 \pmod{p}$이다.
$x^{2} \equiv 1 \pmod{p}$에서 $x^{2} - 1 \equiv 0 \pmod{p}$이고, $(x - 1)(x + 1) \equiv 0 \pmod{p}$이므로
$x \equiv 1 \pmod{p}$이거나 $x \equiv -1 \pmod{p}$임을 쉽게 알 수 있습니다.

$5$이상의 소수 $p$는 $2$이상 $p - 2$이하의 모든 $a$와 서로소 이며 (서로소가 아니라면 소수일 수 없다.) 따라서 베주항등식 에 따라 $ab + pn = 1$ 인 두 정수 $b$, $n$이 존재하고, 모듈로 $p$를 취하면 $ab \equiv 1 \pmod{p}$이다.
이는 $a$의 모듈러 곱셈 역원 $b$이 존재한다는 것인데, 만약 $a = b$이었다면 $a = 1$이거나 $a = p - 1$이어야 하는데, "$2$이상 $p - 2$이하의 모든 $a$" 라는 점에 모순이므로 $b$은 "$2$이상 $p - 2$이하 이면서 $a$와는 다른 어떤 자연수"이다.
모듈러 곱셈 역원의 유일성으로 $ab \equiv ab_{1} \equiv 1 \pmod{p}$이면 $b = b_{1}$이고, 이는 마찬가지로 $b$에 대해서도 $ab \equiv a_{1}b \equiv 1 \pmod{p}$ 이면 $a = a_{1}$이다.
따라서 "$2$이상 $p - 2$이하의 모든 $a$"에게는 그에게 대응되는 짝이 있고, 짝이 총 $\frac{p - 3}{2}$개 이다.
따라서 $2$, $3$, $4$, $5$...$p - 2$의 곱을 잘 배열하면 역원쌍 $\frac{p - 3}{2}$개의 곱으로 만들 수 있으므로, $\prod\limits_{n = 2}^{p - 2} n \equiv 1 \pmod{p}$이다.
$(p - 1)!$은 $1 \times p - 1 \times \prod\limits_{n = 2}^{p - 2} n$라는 것을 이용하여주면, $(p - 1)! = 1 \times p - 1 \times \prod\limits_{n = 2}^{p - 2} n = 1 \times p - 1 \times 1 \equiv p - 1 \pmod{p}$이다.
$p - 1 \equiv -1 \pmod{p}$이므로, 모든 소수 $p$에 대해 $(p - 1)! \equiv -1 \pmod{p}$이다.

"짝을 짓는다" 라는 굉장히 미묘한 표현때문에 거슬리는 분들에게는 다른 증명 방법도 있습니다.
윌슨의 정리 증명 2

(증명의 스케치)
$p$는 소수이므로 원시근 이 존재한다.
$a$를 $p$의 원시근이라 하면, $a^{1}, a^{2}, a^{3}, ... a^{p - 1}$ 를 $p$로 나눈 나머지들을 정렬하면 $1$부터 $p - 1$까지의 모든 자연수가 딱 1번씩 나오게 된다.
따라서, $$ (p - 1)! \equiv \prod\limits_{k = 1}^{p - 1} k \equiv \prod\limits_{k = 1}^{p - 1} a^{k} \equiv a^{\sum\limits_{k = 1}^{p - 1} k} \equiv a^{\frac{p(p - 1)}{2}} \equiv a^{\frac{(p - 1)}{2}p} \pmod{p} $$ 이다. (합 부분은 거듭제곱의 합 으로 계산)
페르마의 소정리 에 따라 $a^{p - 1} \equiv 1 \pmod{p}$이고, $a$가 원시근이므로 $a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$이다.
따라서 $a^{\frac{(p - 1)}{2}p} \equiv {(-1)}^{p} \pmod{p}$이고, $p$는 홀수 소수 이므로 ${(-1)}^{p} \equiv -1 \pmod{p}$이다.

대신 이 증명을 쓰려면 원시근 관련 성질이나 페르마의 소정리를 증명할 때 윌슨의 정리를 사용하면 안됩니다.

윌슨의 정리로 소수판별?

정수론 문제 풀 때는 윌슨의 정리가 쓸만할 수 있어도, 일반적인 소수판별에는 전혀 쓸모가 없습니다.
어떤 자연수 $N$에 대하여, $(N - 1)! \equiv -1 \pmod{N}$ 인지 확인해보려 하면, $1$부터 $N - 1$ 까지 곱하면서 계속 $N$으로 나눠가는 수밖에 없습니다.
차라리 $\sqrt{N}$까지 나눠보는 소수판별법 이 $\sqrt{N}$배 더 빠릅니다.