윌슨의 정리
Wilson's Theorem.
1. 개요
대부분의 정수론 교재에 등장하는 정리. 이름은 수학자 존 윌슨의 이름을 땄다. 1770년에 수학자 에드워드 웨어링(Edward Waring)이 이 정리를 발표했으나, 자기 자신이나 제자 윌슨도 증명을 하지 못했다. 일단 공식적인 첫 증명은 1771년에 라그랑주에 의해 발표되었다. 자세한 정리는 아래와 같다.
이 방법은 소수 판정법에 이용할 수 있으나 팩토리얼을 구하는 시간에 1부터 제곱근까지 하나씩 나눠보는 게 빠르다.$$p$$가 소수일 때, $$\left(p-1\right)!\equiv-1\left(\text{mod}\,p\right)$$가 성립한다. 또한, 그 역도 성립한다.
2. 증명
증명에 앞서 합동식에 관한 내용과 잉여계, 잉여역수에 관한 내용을 꼭 알아야 한다. 먼저 도움정리부터 증명하자.
2.1. 도움정리
증명$$p$$가 소수이고, $$k$$는 $$0<k<p$$인 정수라고 할 때, $$k^2\equiv1\left(\text{mod}\,p\right)$$이면 $$k=1$$ 또는 $$k=p-1$$이다. 그 역도 성립한다.
2.2. 증명
$$p$$가 소수라고 가정하자. 그럼 임의의 $$k\in\left\{1,2,\cdots,p-1\right\}$$에 대하여 $$k$$와 $$p$$는 서로소이다. 그러므로 적당한 정수 $$a,b$$에 대해 $$ak+bp=1$$이 성립하고,[1] 곧 $$ak\equiv1\left(\text{mod}\,p\right)$$이다. 법 $$p$$에 대하여 $$a\in\left\{1,2,\cdots,p-1\right\}$$이므로 $$\left\{1,2,\cdots,p-1\right\}$$의 모든 원소의 법 $$p$$에 대한 잉여역수는 같은 집합의 원소이다. 특히, 도움정리에 의해 $$1$$과 $$p-1$$은 자기 자신이 잉여역수이다. 나머지 $$2,3,\cdots,p-2$$는 두 원소씩 쌍으로 법 $$p$$에 대해 잉여역수 관계이고, 따라서 $$\left(p-1\right)!\equiv1\cdot2\cdots\left(p-2\right)\cdot\left(p-1\right)\equiv1\cdot1\cdot\left(p-1\right)\equiv p-1\equiv -1\left(\text{mod}\,p\right)$$이다.
역으로 $$\left(p-1\right)!\equiv-1\left(\text{mod}\,p\right)$$라고 가정하자. 그러면 $$\left(p-1\right)!+1=kp$$를 만족하는 정수 $$k$$가 존재한다. $$p=ab,\,\left(1\leq a,b\leq p\right)$$라 가정하자. 만약 $$a=p$$이면 $$b=1$$이고 이는 곧 $$p$$가 소수임을 의미한다. $$a<p$$라고 가정하면, $$a\in\left\{1,2,\cdots,p-1\right\}$$이므로 $$a\mid\left(p-1\right)!$$이다. 그리고 $$a\mid p$$이고, $$\left(p-1\right)!+1=kp$$이므로 $$a\mid1$$이다. 이를 모두 만족하는 값은 $$a=1$$밖에 없고, 따라서 $$b=p$$이다. 곧 $$p$$는 소수이다.
3. 예시
17!을 19로 나눈 나머지를 구해보자. 먼저 정리를 쓰면, $$18!\equiv-1\left(\text{mod}\,19\right)$$이다. 또한, $$18\equiv-1\left(\text{mod}\,19\right)$$이므로, $$-1\equiv18!\equiv18\times17!\equiv\left(-1\right)\times17!\left(\text{mod}\,19\right)$$이다. 따라서 $$17!\equiv1\left(\text{mod}\,19\right)$$이다.