윌슨의 정리

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))

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

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

4. 3. 다양한 증명 방법

• '''초등적인 증명''': ''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''을 계산하는 것이 계산적으로 복잡하고 훨씬 더 빠른 소수 판정법이 알려져 있기 때문에 소수 판정법으로서는 쓸모가 없다.^[1]

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

윌슨의 정리를 이용하면, 임의의 홀수 소수 ''p'' = 2''m'' + 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'' = 4''k'' + 1이라고 가정하자. 그러면 위에서 ''m'' = 2''k''를 취할 수 있으며, (''m''!)²이 (−1)과 합동임을 (mod ''p'') 결론지을 수 있다.

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

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

7. 가우스의 일반화

Carl Friedrich Gauss|카를 프리드리히 가우스^de[7]는 다음을 증명했다.

:$$$$

\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] 서적 The Universal Book of Mathematics
_[2] 웹사이트 Abu Ali al-Hasan ibn al-Haytham
_[3] 서적 Meditationes Algebraicae https://books.google[...] Cambridge, England
_[4] 간행물 Demonstration d'un théorème nouveau concernant les nombres premiers https://books.google[...]
_[5] 간행물 Sui manoscritti inediti di Leibniz https://books.google[...]
_[6] 서적 two proofs of thm. 78
_[7] 서적 DA, art. 78
_[8] 웹사이트 Abu Ali al-Hasan ibn al-Haytham
_[9] 웹사이트 John Wilson
_[10] 문서 WilsonsTheorem