윌슨의 정리

1. 개요

윌슨의 정리는 10세기 이븐 알하이삼에 의해 처음 언급되었고, 1770년 에드워드 워링에 의해 제자 존 윌슨이 발견했다고 발표되면서 윌슨의 정리로 명명되었다. 이 정리는 소수 p에 대해 (p-1)! + 1이 p로 나누어 떨어진다는 것을 나타내며, 윌슨의 정리는 소수 판별법으로 이론적으로 사용될 수 있지만, 계산 복잡성으로 인해 실용적이지 않다. 또한, 윌슨의 정리는 p-adic 감마 함수를 정의하거나 가우스의 일반화를 통해 확장되어 활용될 수 있다.

2. 역사

윌슨의 정리는 10세기 페르시아의 수학자 이븐 알하이삼에 의해 처음 언급되었다. 유럽에서는 오랫동안 알려지지 않다가, 1770년 영국의 에드워드 워링이 그의 제자 존 윌슨이 발견했다고 발표하면서 "윌슨의 정리"라는 이름이 붙었다. 1771년에 조제프 루이 라그랑주가 처음으로 증명을 제시했다. 고트프리트 빌헬름 라이프니츠도 한 세기 전에 이 결과를 알고 있었지만, 발표하지는 않았다.

3. 예시

2부터 30까지의 각 n 값에 대해, (n − 1)!의 값과 (n − 1)!을 n으로 나눈 나머지를 나타내는 표이다. (모듈러 산술 표기법에서, m을 n으로 나눈 나머지는 m mod n으로 표기한다.) 배경색은 n이 소수일 경우 파란색, 합성수일 경우 금색이다.

4. 증명

윌슨의 정리는 쌍조건문(필요충분조건)이므로, 증명은 $n$이 소수일 때 등식이 성립함을 보이는 부분과 $n$이 합성수일 때 등식이 성립하지 않음을 보이는 두 부분으로 나뉜다.

4.1. 필요조건의 증명 (n이 소수이면 (n - 1)! ≡ -1 (mod n))

$p$가 소수이면, $p$의 기약잉여계 $G\; =\; (\backslash mathbb\{Z\}\; /\; p\; \backslash mathbb\{Z\})^\backslash times\; \backslash equiv\; \backslash \{1,\; 2,\; 3,\; \backslash ldots,\; (p-1)\backslash \}$는 $p$에 대한 가환환을 이룬다.

이는 $G$의 임의의 원소 $i$에 대하여, $ij\; \backslash equiv\; 1\; \backslash pmod\{p\}$이 성립하는 역원 $j$가 존재한다는 것이다.

만약 $i\; \backslash equiv\; j\; \backslash pmod\{p\}$이면,

:$\backslash begin\{alignat\}\{2\}$
i^2 \equiv 1 \pmod{p} & \Longrightarrow\ i^2 - 1 \equiv (i-1)(i+1) \equiv 0 \pmod{p}
\\ & \Longrightarrow i \equiv 1\ \mathrm{or}\ (p-1)
\\ \end{alignat}

이와 같이 $1$ 과 $p-1$만이 자기 자신을 곱의 역원으로 가지고, 나머지 원소들은 자신이 아닌 다른 원소를 역원으로 갖는다.

따라서, $1$ 과 $p-1$을 제외한 원소들을 모두 곱하면 법 $p$에 대해 1과 합동이 되고, $G$의 원소들을 모두 곱한 값, 즉 $(p-1)!$의 값은 −1과 합동이 된다.

예를 들어, $p=11$ 인 경우:

:$10!\; =\; (1)(10)(2\; \backslash cdot\; 6)(3\; \backslash cdot\; 4)(5\; \backslash cdot\; 9)(7\; \backslash cdot\; 8)\; \backslash \; \backslash equiv\backslash \; -1\; \backslash pmod\{11\}$

로 성립하며, $p=2$인 경우 $(2-1)!\; =\; 1\; \backslash equiv\; -1\; \backslash pmod\{2\}$가 된다.

:$\backslash therefore\; p\; \backslash in\; \backslash mathbb\{P\}\backslash \; \backslash Longrightarrow\; (p-1)!\; \backslash equiv\; 1\; \backslash pmod\{p\}$ (단, $\backslash mathbb\{P\}$는 소수들의 집합)

이 증명은 소수를 법(modulus)으로 하는 잉여류가 유한체를 이룬다는 사실을 이용한다. p = 2일 때는 결과가 자명하므로, p가 3 이상의 홀수 소수라고 가정한다. p를 법으로 하는 잉여류는 체를 이루므로, 0이 아닌 모든 잉여 a는 유일한 곱셈적 역원 a⁻¹을 갖는다. 유클리드의 보조정리에 의해 a ≡ a⁻¹ (mod p)인 a의 값은 a ≡ ±1 (mod p) 뿐이다. 따라서 ±1을 제외하고 (p - 1)!의 전개된 형태의 인수들은 각 쌍의 곱이 1 (mod p)가 되도록 서로소인 쌍으로 배열될 수 있다.

예를 들어, p = 11일 때, 다음과 같다.
:$10!\; =\; [(1\backslash cdot10)]\backslash cdot[(2\backslash cdot6)(3\backslash cdot4)(5\backslash cdot9)(7\backslash cdot8)]\; \backslash equiv\; [-1]\backslash cdot[1\backslash cdot1\backslash cdot1\backslash cdot1]\; \backslash equiv\; -1\; \backslash pmod\{11\}.$

4.2. 충분조건의 증명 ((n - 1)! ≡ -1 (mod n)이면 n은 소수)

$(n-1)!\; \backslash equiv\; -1\; \backslash pmod\; n$인 합성수 $n$이 존재한다고 가정하자.

$n$이 합성수이므로 인 $n$의 약수 $q$를 잡을 수 있다.

* $q\; |\; n$이며 $n\; |\; (n-1)!\; +\; 1$이므로 $q\; |\; (n-1)!\; +\; 1$이다.
* $q\; \backslash le\; (n-1)$이므로 $q\; |\; (n-1)!$이다.

즉, $q$는 $(n-1)!\; +\; 1$과 $(n-1)!$의 공약수인데, 이는 $(n-1)!\; +\; 1$과 $(n-1)!$가 서로소임에 모순된다.

따라서 귀류법을 통해 조건을 만족하는 $n$은 모두 소수임을 알 수 있다.

4.3. 다양한 증명 방법

Edward Waring^영어은 1770년에 이 정리를 증명 없이 발표했으며, 그의 제자인 John Wilson (mathematician and judge)^영어이 발견했다고 언급했다. Joseph Louis Lagrange^프랑스어는 1771년에 처음으로 증명을 제시했다.

* 초등적인 증명: p = 2일 때는 결과가 자명하므로, p가 3 이상의 홀수 소수라고 가정한다. p를 법으로 하는 잉여류는 체를 이루므로, 0이 아닌 모든 잉여 a는 유일한 곱셈적 역원 a^-1을 갖는다. 유클리드의 보조정리에 의해, a ≡ a^-1 (mod p)인 a의 값은 a ≡ ±1 (mod p) 뿐이다. 따라서 ±1을 제외하고 (p - 1)!의 전개된 형태의 인수들은 각 쌍의 곱이 1 (mod p)가 되도록 서로소인 쌍으로 배열될 수 있다.

* 페르마의 소정리를 이용한 증명: p = 2일 때 결과는 자명하므로, p가 홀수 소수라고 가정한다 (p ≥ 3). 다항식 g(x) = (x - 1)(x - 2) ⋯ (x - (p - 1))를 생각하면, g는 차수가 p − 1이고, 최고차항은 x^{p − 1}이며, 상수항은 (p − 1)!이다. h(x) = x^p-1 - 1 또한 같은 차수와 최고차항을 가지며, 페르마의 소정리에 의해 g와 같은 p − 1개의 근을 갖는다. f(x) = g(x) - h(x)는 최고차항이 상쇄되어 최대 p − 2의 차수를 가지지만, 소수 p를 법으로 하면 p − 1개의 근을 갖는다. 라그랑주 정리에 따르면, p − 2개보다 많은 근을 가질 수 없으므로 f는 항등적으로 0 (mod p)이어야 하며, 따라서 그 상수항은 (p − 1)! + 1 ≡ 0 (mod p)이다.

* 실로우 정리를 이용한 증명: 소수 p에 대해, 대칭군 $S\_p$는 위수 p인 원소를 정확히 $(p-1)!$개 갖는다. $S\_p$의 각 실로우 p-부분군은 $C\_p$의 복사본이므로, 실로우 p-부분군의 개수는 $n\_p=(p-2)!$이다. 세 번째 실로우 정리에 의해, $(p-2)!\; \backslash equiv\; 1\; \backslash pmod\; p$가 성립하며, 양변에 p − 1을 곱하면 $(p-1)!\; \backslash equiv\; p-1\; \backslash equiv\; -1\; \backslash pmod\; p$를 얻는다.

* 원시근을 이용한 증명: p = 2인 경우는 명백히 성립하므로, p는 홀수인 소수라고 가정한다. p는 소수이므로 법 p에 대한 원시근 a가 존재한다. 페르마의 소정리에 의해, a^p−1 ≡ 1 (mod p)이다. a는 원시근이므로, a¹, a², ..., a^p−1(≡1)은 각각 p를 법으로 환원하면 1, 2, ..., p − 1의 순열이다. 따라서, a¹a²⋯a^p−1 ≡ (p-1)! (mod p)이다. 한편, a¹a²⋯a^p−1 = a^{1+2+⋯+(p−1)} = a^p(p−1)/2이다. b = a^p(p−1)/2라고 하면, b² ≡ 1 (mod p)이므로 b ≡ ±1 (mod p)이다. b ≡ −1 (mod p)임을 보이기 위해 b ≡ 1 (mod p)라고 가정하면, a는 원시근이므로 p(p−1)/2는 p−1로 나누어떨어진다. 따라서 p/2는 정수가 되지만, 이것은 p가 홀수라는 것에 모순된다.

5. 따름 정리

임의의 소수 $p$에 대해,

:$(p-2)!\; =\; (p-1)!\; \backslash cdot\; (p-1)^\{-1\}\; \backslash equiv\; (-1)\; \backslash cdot\; (-1)\; \backslash equiv\; 1\; \backslash pmod\{p\}$

가 성립한다.

6. 응용

윌슨의 정리는 큰 n^영어에 대해 (n − 1)! mod n을 계산하는 것이 계산적으로 복잡하고 훨씬 더 빠른 소수 판정법이 알려져 있기 때문에 소수 판정법으로서는 쓸모가 없다.

반대로, 큰 계승의 다음 수의 소수성을 결정하는 데 사용하면 매우 빠르고 효과적인 방법이다. 그러나 이것은 활용도가 제한적이다.

윌슨의 정리를 이용하면, 임의의 홀수 소수 p = 2m + 1에 대해, 다음 식의 좌변을 재배열할 수 있다.

:1·2⋯(p−1) ≡ −1 (mod p)

이는 다음과 같은 등식을 얻는다.

:1·(p−1)·2·(p−2)⋯m·(p−m) ≡ 1·(−1)·2·(−2)⋯m·(−m) ≡ −1 (mod p).

이는 다음과 같이 된다.

:$\backslash prod\_\{j=1\}^m\backslash \; j^2\backslash \; \backslash equiv(-1)^\{m+1\}\; \backslash pmod\{p\}$

또는

:(m!)² ≡ (−1)^m+1 (mod p).

이 사실을 이용하여 p ≡ 1 (mod 4)인 모든 소수 p에 대해, 수 (−1)은 p를 법으로 하는 제곱잉여이다. 이를 위해, 어떤 정수 k에 대해 p = 4k + 1이라고 가정하자. 그러면 위에서 m = 2k를 취할 수 있으며, (m!)²이 (−1)과 합동임을 (mod p) 결론지을 수 있다.

윌슨의 정리는 소수 공식을 구성하는 데 사용되었지만, 너무 느려서 실용적인 가치가 없다.

윌슨 정리는 p-adic 감마 함수를 정의하는 데 사용할 수 있다.

7. 가우스의 일반화

Carl Friedrich Gauss^독일어는 다음을 증명했다.

:$$$$
\prod_{k = 1 \atop \gcd(k,m)=1}^m \!\!k \ \equiv
\begin{cases}
-1 \pmod{m} & \text{if } m=4,\;p^\alpha,\;2p^\alpha \\
\;\;\,1 \pmod{m} & \text{otherwise}
\end{cases}


여기서 p는 홀수 소수이고, $\backslash alpha$는 양의 정수이다. 즉, m보다 작고 m와 서로소인 양의 정수들의 곱은 m이 4이거나, 홀수 소수의 거듭제곱이거나, 홀수 소수의 거듭제곱의 두 배일 때 m의 배수보다 1 작고, 그렇지 않으면 m의 배수보다 1 크다. 곱이 -1인 m의 값은 모듈로 m에 대한 원시근이 존재하는 값들이다.