Processing math: 100%

윌슨의 정리

Wilson's Theorem.

1 개요

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

p가 소수일 때, (p1)!1(modp)가 성립한다. 또한, 그 역도 성립한다.

2 증명

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

2.1 도움정리

p가 소수이고, k0\ltk\ltp인 정수라고 할 때, k21(modp)이면 k=1 또는 k=p1이다. 그 역도 성립한다.

증명

k=1이면 k21(modp)이다. 또한, k=p1이면, k2=p22p+11(modp)이다.
역으로, k21(modp)라고 가정하자. 그러면 p(k21)=(k1)(k+1)이다. p소수이므로, p(k1)또는 p(k+1)이다. p(k1)를 만족하는 p이하의 양의 정수 k는 오직 1뿐이고, p(k+1)을 만족하는 p이하의 양의 정수 k는 오직 p1뿐이다.

2.2 증명

p가 소수라고 가정하자. 그럼 임의의 k{1,2,,p1}에 대하여 kp서로소이다. 그러므로 적당한 정수 a,b에 대해 ak+bp=1이 성립하고,[1]ak1(modp)이다. 법 p에 대하여 a{1,2,,p1}이므로 {1,2,,p1}의 모든 원소의 법 p에 대한 잉여역수는 같은 집합의 원소이다. 특히, 도움정리에 의해 1p1은 자기 자신이 잉여역수이다. 나머지 2,3,,p2는 두 원소씩 쌍으로 법 p에 대해 잉여역수 관계이고, 따라서 (p1)!12(p2)(p1)11(p1)p11(modp)이다.

역으로 (p1)!1(modp)라고 가정하자. 그러면 (p1)!+1=kp를 만족하는 정수 k가 존재한다. p=ab,(1a,bp)라 가정하자. 만약 a=p이면 b=1이고 이는 곧 p가 소수임을 의미한다. a\ltp라고 가정하면, a{1,2,,p1}이므로 a(p1)!이다. 그리고 ap이고, (p1)!+1=kp이므로 a1이다. 이를 모두 만족하는 값은 a=1밖에 없고, 따라서 b=p이다. 곧 p소수이다.

3 예시

17!을 19로 나눈 나머지를 구해보자. 먼저 정리를 쓰면, 18!1(mod19)이다. 또한, 181(mod19)이므로, 118!18×17!(1)×17!(mod19)이다. 따라서 17!1(mod19)이다.

4 관련 항목

  1. 이동 최대공약수 항목 참조