Wilson's Theorem.
1 개요
대부분의 정수론 교재에 등장하는 정리. 이름은 수학자 존 윌슨의 이름을 땄다. 1770년에 수학자 에드워드 웨어링(Edward Waring)이 이 정리를 발표했으나, 자기 자신이나 제자 윌슨도 증명을 하지 못했다.그럼 도대체 왜 발표한거야 일단 공식적인 첫 증명은 1771년에 라그랑주에 의해 발표되었다. 그런데 이름은 윌슨의 정리. 라그랑주 안습 자세한 정리는 아래와 같다.
p가 소수일 때, (p−1)!≡−1(modp)가 성립한다. 또한, 그 역도 성립한다.
2 증명
증명에 앞서 합동식에 관한 내용과 잉여계, 잉여역수에 관한 내용을 꼭 알아야 한다. 먼저 도움정리부터 증명하자.
2.1 도움정리
p가 소수이고, k는 0\ltk\ltp인 정수라고 할 때, k2≡1(modp)이면 k=1 또는 k=p−1이다. 그 역도 성립한다.
증명
k=1이면 k2≡1(modp)이다. 또한, k=p−1이면, k2=p2−2p+1≡1(modp)이다.
역으로, k2≡1(modp)라고 가정하자. 그러면 p∣(k2−1)=(k−1)(k+1)이다. p가 소수이므로, p∣(k−1)또는 p∣(k+1)이다. p∣(k−1)를 만족하는 p이하의 양의 정수 k는 오직 1뿐이고, p∣(k+1)을 만족하는 p이하의 양의 정수 k는 오직 p−1뿐이다.
2.2 증명
p가 소수라고 가정하자. 그럼 임의의 k∈{1,2,⋯,p−1}에 대하여 k와 p는 서로소이다. 그러므로 적당한 정수 a,b에 대해 ak+bp=1이 성립하고,[1] 곧 ak≡1(modp)이다. 법 p에 대하여 a∈{1,2,⋯,p−1}이므로 {1,2,⋯,p−1}의 모든 원소의 법 p에 대한 잉여역수는 같은 집합의 원소이다. 특히, 도움정리에 의해 1과 p−1은 자기 자신이 잉여역수이다. 나머지 2,3,⋯,p−2는 두 원소씩 쌍으로 법 p에 대해 잉여역수 관계이고, 따라서 (p−1)!≡1⋅2⋯(p−2)⋅(p−1)≡1⋅1⋅(p−1)≡p−1≡−1(modp)이다.
역으로 (p−1)!≡−1(modp)라고 가정하자. 그러면 (p−1)!+1=kp를 만족하는 정수 k가 존재한다. p=ab,(1≤a,b≤p)라 가정하자. 만약 a=p이면 b=1이고 이는 곧 p가 소수임을 의미한다. a\ltp라고 가정하면, a∈{1,2,⋯,p−1}이므로 a∣(p−1)!이다. 그리고 a∣p이고, (p−1)!+1=kp이므로 a∣1이다. 이를 모두 만족하는 값은 a=1밖에 없고, 따라서 b=p이다. 곧 p는 소수이다.
3 예시
17!을 19로 나눈 나머지를 구해보자. 먼저 정리를 쓰면, 18!≡−1(mod19)이다. 또한, 18≡−1(mod19)이므로, −1≡18!≡18×17!≡(−1)×17!(mod19)이다. 따라서 17!≡1(mod19)이다.