윌슨의 정리

Wilson's Theorem.

1 개요

대부분의 정수론 교재에 등장하는 정리. 이름은 수학자 존 윌슨의 이름을 땄다. 1770년에 수학자 에드워드 웨어링(Edward Waring)이 이 정리를 발표했으나, 자기 자신이나 제자 윌슨도 증명을 하지 못했다.그럼 도대체 왜 발표한거야 일단 공식적인 첫 증명은 1771년에 라그랑주에 의해 발표되었다. 그런데 이름은 윌슨의 정리. 라그랑주 안습 자세한 정리는 아래와 같다.

[math]p[/math]가 소수일 때, [math]\left(p-1\right)!\equiv-1\left(\text{mod}\,p\right)[/math]가 성립한다. 또한, 그 역도 성립한다.

2 증명

증명에 앞서 합동식에 관한 내용과 잉여계, 잉여역수에 관한 내용을 꼭 알아야 한다. 먼저 도움정리부터 증명하자.

2.1 도움정리

[math]p[/math]가 소수이고, [math]k[/math][math]0\ltk\ltp[/math]인 정수라고 할 때, [math]k^2\equiv1\left(\text{mod}\,p\right)[/math]이면 [math]k=1[/math] 또는 [math]k=p-1[/math]이다. 그 역도 성립한다.

증명

[math]k=1[/math]이면 [math]k^2\equiv1\left(\text{mod}\,p\right)[/math]이다. 또한, [math]k=p-1[/math]이면, [math]k^2=p^2-2p+1\equiv1\left(\text{mod}\,p\right)[/math]이다.
역으로, [math]k^2\equiv1\left(\text{mod}\,p\right)[/math]라고 가정하자. 그러면 [math]p\mid\left(k^2-1\right)=\left(k-1\right)\left(k+1\right)[/math]이다. [math]p[/math]소수이므로, [math]p\mid\left(k-1\right)[/math]또는 [math]p\mid\left(k+1\right)[/math]이다. [math]p\mid\left(k-1\right)[/math]를 만족하는 [math]p[/math]이하의 양의 정수 [math]k[/math]는 오직 1뿐이고, [math]p\mid\left(k+1\right)[/math]을 만족하는 [math]p[/math]이하의 양의 정수 [math]k[/math]는 오직 [math]p-1[/math]뿐이다.

2.2 증명

[math]p[/math]가 소수라고 가정하자. 그럼 임의의 [math]k\in\left\{1,2,\cdots,p-1\right\}[/math]에 대하여 [math]k[/math][math]p[/math]서로소이다. 그러므로 적당한 정수 [math]a,b[/math]에 대해 [math]ak+bp=1[/math]이 성립하고,[1][math]ak\equiv1\left(\text{mod}\,p\right)[/math]이다. 법 [math]p[/math]에 대하여 [math]a\in\left\{1,2,\cdots,p-1\right\}[/math]이므로 [math]\left\{1,2,\cdots,p-1\right\}[/math]의 모든 원소의 법 [math]p[/math]에 대한 잉여역수는 같은 집합의 원소이다. 특히, 도움정리에 의해 [math]1[/math][math]p-1[/math]은 자기 자신이 잉여역수이다. 나머지 [math]2,3,\cdots,p-2[/math]는 두 원소씩 쌍으로 법 [math]p[/math]에 대해 잉여역수 관계이고, 따라서 [math]\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)[/math]이다.

역으로 [math]\left(p-1\right)!\equiv-1\left(\text{mod}\,p\right)[/math]라고 가정하자. 그러면 [math]\left(p-1\right)!+1=kp[/math]를 만족하는 정수 [math]k[/math]가 존재한다. [math]p=ab,\,\left(1\leq a,b\leq p\right)[/math]라 가정하자. 만약 [math]a=p[/math]이면 [math]b=1[/math]이고 이는 곧 [math]p[/math]가 소수임을 의미한다. [math]a\ltp[/math]라고 가정하면, [math]a\in\left\{1,2,\cdots,p-1\right\}[/math]이므로 [math]a\mid\left(p-1\right)![/math]이다. 그리고 [math]a\mid p[/math]이고, [math]\left(p-1\right)!+1=kp[/math]이므로 [math]a\mid1[/math]이다. 이를 모두 만족하는 값은 [math]a=1[/math]밖에 없고, 따라서 [math]b=p[/math]이다. 곧 [math]p[/math]소수이다.

3 예시

17!을 19로 나눈 나머지를 구해보자. 먼저 정리를 쓰면, [math]18!\equiv-1\left(\text{mod}\,19\right)[/math]이다. 또한, [math]18\equiv-1\left(\text{mod}\,19\right)[/math]이므로, [math]-1\equiv18!\equiv18\times17!\equiv\left(-1\right)\times17!\left(\text{mod}\,19\right)[/math]이다. 따라서 [math]17!\equiv1\left(\text{mod}\,19\right)[/math]이다.

4 관련 항목

  1. 최대공약수 항목 참조