윌슨의 정리

위키백과 ― 우리 모두의 백과사전.

윌슨의 정리(Wilson's Theorem)는 1보다 큰 소수 p에 대해서

(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)

이 성립한다는 정수론의 정리이다.

목차

[편집] 역사

이 정리는 영국의 수학자 에드워드 워링의 학생이었던 존 윌슨이 처음 발견하였고, 워링은 이 정리를 증명없이 1770년에 발표하였다. 이 정리를 최초로 증명해 낸 것은 1773년 라그랑주에 의해서였다. 한 세기 이전에 고트프리트 라이프니츠 또한 이 정리를 알고 있었다는 증거가 있으나 그는 이 사실을 발표하지 않았다.

[편집] 증명

만약 p가 3 이상의 소수이면, G = (Z/pZ)× = {1, 2, ... p − 1} 은 p에 대한 곱셈 연산 군을 이룬다. 이것은 G의 임의의 원소 i에 대하여, ij ≡ 1 (mod p) 이 성립하는 역원 j가 존재한다는 것이다.

만약 ij (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 인 경우의 값은:

10! = 1(10)(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11)

그리고 p = 2인 경우는 (2 − 1)! = -1 (mod 2) 가 된다.

역을 증명해보자. 합성수 n이 윌슨의 정리를 만족한다고 할 때, n의 약수이고 1과 n 사이의 정수 d가 존재한다. 그러면 d는 (n − 1)!의 약수이고, 그리고 가정에 의해 d는 (n − 1)! + 1의 약수이다, 그러면 d는 1의 약수가 되고, 이는 처음과 모순된다.

[편집] 일반화

가우스가 윌슨의 정리를 일반화한 것이 있다:

\prod_{\begin{matrix} 1 \le a < m \\ (a,m)=1 \end{matrix}} a \ \equiv \ \left \{ \begin{matrix} -1\ (\mbox{mod }m) & \mbox{if } m=4,\;p^\alpha,\;2p^\alpha \\ \ \ 1\ (\mbox{mod }m) & \mbox{otherwise} \end{matrix} \right.

여기에서 p 는 홀수인 소수.

[편집]

윌슨의 정리의 역은 5보다 큰 합성수 n에 대해, 다음과 같이 나타낼 수 있다:

n은 (n − 1)!의 약수.

n = 4일 경우는 예외이다. ( 3! = 2 (mod 4) ).