윌슨의 정리
위키백과 ― 우리 모두의 백과사전.
윌슨의 정리(Wilson's Theorem)는 1보다 큰 소수 p에 대해서
이 성립한다는 정수론의 정리이다.
목차 |
[편집] 역사
이 정리는 영국의 수학자 에드워드 워링의 학생이었던 존 윌슨이 처음 발견하였고, 워링은 이 정리를 증명없이 1770년에 발표하였다. 이 정리를 최초로 증명해 낸 것은 1773년 라그랑주에 의해서였다. 한 세기 이전에 고트프리트 라이프니츠 또한 이 정리를 알고 있었다는 증거가 있으나 그는 이 사실을 발표하지 않았다.
[편집] 증명
만약 p가 3 이상의 소수이면, G = (Z/pZ)× = {1, 2, ... p − 1} 은 p에 대한 곱셈 연산 군을 이룬다. 이것은 G의 임의의 원소 i에 대하여, ij ≡ 1 (mod p) 이 성립하는 역원 j가 존재한다는 것이다.
만약 i ≡ j (mod p) 이면, i2 ≡ 1 (mod p) 이 되고, i2 − 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 인 경우의 값은:
그리고 p = 2인 경우는 (2 − 1)! = -1 (mod 2) 가 된다.
역을 증명해보자. 합성수 n이 윌슨의 정리를 만족한다고 할 때, n의 약수이고 1과 n 사이의 정수 d가 존재한다. 그러면 d는 (n − 1)!의 약수이고, 그리고 가정에 의해 d는 (n − 1)! + 1의 약수이다, 그러면 d는 1의 약수가 되고, 이는 처음과 모순된다.
[편집] 일반화
가우스가 윌슨의 정리를 일반화한 것이 있다:
여기에서 p 는 홀수인 소수.
[편집] 역
윌슨의 정리의 역은 5보다 큰 합성수 n에 대해, 다음과 같이 나타낼 수 있다:
- n은 (n − 1)!의 약수.
n = 4일 경우는 예외이다. ( 3! = 2 (mod 4) ).