윌슨의 정리

윌슨의 정리(Wilson's Theorem)는 1보다 큰 소수 $p$에 대해서

$(p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)$

이 성립한다는 정수론의 정리이다.

증명

만약 p가 3 이상의 소수이면, G = (Z/pZ)^× = {1, 2, ... p − 1} 은 p에 대한 곱셈 연산 군을 이룬다. 이것은 G의 임의의 원소 i에 대하여, ij ≡ 1 (mod p) 이 성립하는 역원 j가 존재한다는 것이다.

만약 i ≡ j (mod p) 이면, i² ≡ 1 (mod p) 이 되고, i² − 1 = (i + 1)(i − 1) ≡ 0 (mod p) 이므로, i = 1 or p − 1 이 된다.

이와 같이 1과 p −1은 역원이 그 자신이고, 나머지 원소들은 자신과 다른 원소를 역원으로 갖는다. 따라서, 1과 −1을 제외한 원소들을 모두 곱하면 1이 되고, G의 원소들을 모두 곱한 값, 즉 (p − 1)!의 값은 −1이 된다.

예를 들어, p = 11 인 경우의 값은:

$10!=1(10)(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)\ \equiv \ -1\ ({\mbox{mod}}\ 11)$

그리고 p = 2인 경우는 (2 − 1)! = -1 (mod 2) 가 된다.

역을 증명해보자. 합성수 n이 윌슨의 정리를 만족한다고 할 때, n의 약수이고 1과 n 사이의 정수 d가 존재한다. 그러면 d는 (n − 1)!의 약수이고, 그리고 가정에 의해 d는 (n − 1)! + 1의 약수이다, 그러면 d는 1의 약수가 되고, 이는 처음과 모순된다.

역

윌슨의 정리의 역은 5보다 큰 합성수 n에 대해, 다음과 같이 나타낼 수 있다:

n은 (n − 1)!의 약수.

n = 4일 경우는 예외이다. ( 3! = 2 (mod 4) ).

역의 증명

윌슨의 정리의 역은 다음과 같이 증명할 수 있다.

1) p=1이면 0! = -1 (mod 1)이 성립하지 않으므로 모순

2) p=합성수이면 1<u≤p-1이며 uㅣp인 u가 존재한다고 할 수 있다.

그러므로 uㅣ(p-1)!이며 이는 uㅣ(p-1)! + 1이 성립하지 않는다는 걸 보여준다.

또 uㅣp에서 위의 식은 pㅣ(p-1)! + 1이 성립하지 않음으로 바뀔 수 있으며 이는

(p-1)! = -1 (mod p)가 성립하지 않음을 증명한다.

그러므로 p는 1과 합성수가 아닌 자연수, 즉 소수임이 증명된다.