윌슨 정리

수론에서, **윌슨 정리**(Wilson's theorem)는 임의의 소수 p에 대하여, p-1의 계승이 법 p에 대하여 −1과 합동이라는 정리이다.
# 정의
**윌슨 정리**에 따르면, 임의의 자연수 p>1에 대하여, 다음 두 조건이 서로 동치이다. * p는 소수이다. * (p-1)!\equiv-1\pmod p 여기서 !는 계승이며, \equiv\pmod p는 법 p에 대한 합동이다. 두 번째 조건은 약수 관계를 사용하여 :p\mid(p-1)!+1 로 바꿔 쓸 수 있다. 나머지의 개념을 사용하면, (p-1)!를 p로 나눈 나머지가 p-1이라고 바꿔 말할 수 있다. 윌슨 정리는 p>1가 소수일 필요충분조건을 제시한다. 물론, 계승의 계산은 오래 걸리므로 충분조건 부분을 통해 소수를 판별하는 것은 매우 느리다.
# 증명

## 필요조건의 증명
p=2인 경우는 자명하다. 만약 p가 3 이상의 소수라면, 법 p에 대한 합동류들로 구성된 가환환 \mathbb Z/p\mathbb Z는 체를 이룬다. 즉, 임의의 i=1,\dots,p-1에 대하여, :ii^{-1}\equiv1\pmod p 인 i^{-1}=1,\dots,p-1가 존재한다. i^{-1}는 i의 법 p에 대한 곱셈 역원이다. 역원은 유일하며, 역원의 역원은 스스로와 같다. 따라서, 정수 1,\dots,p-1들을 서로 역원인 것들끼리 짝을 지을 수 있다. 다만, 스스로의 역원인 것들은 혼자 짝을 이룬다. 스스로의 역원인 조건 i=i^{-1}은 곧 조건 :i^2\equiv1\pmod p 와 같다. 이는 양변에서 1을 빼 얻는 조건 :(i-1)(i+1)\equiv0\pmod p 와 동치이다. \mathbb Z/p\mathbb Z가 정역이므로, 이는 다시 :i-1\equiv0\pmod p 이거나 :i+1\equiv0\pmod p 인 것과 동치이다. i=1,\dots,p-1이므로, 전자는 i=1이며, 후자는 i=p-1이다. 이제 모든 1,\dots,p-1의 곱을 생각하자. 1과 p-1을 제외한 것들은 역원끼리 짝을 지어 곱하면 1과 합동이 되므로, 1과 p-1만 남는다. 즉, :(p-1)! \equiv 1\cdot(p-1) \equiv -1 \pmod p 이다. 예를 들어, p=11인 경우 :10! = 1\cdot10\cdot(2 \cdot 6)\cdot(3 \cdot 4)\cdot(5 \cdot 9)\cdot(7 \cdot 8) \equiv -1 \pmod{11} 이다.
## 충분조건의 증명
이제 p>1이 1보다 큰 양의 정수이며, :(p-1)! \equiv -1 \pmod p 이며, q가 1\le q\le p-1인 p의 약수라고 가정하자. 그렇다면 다음이 성립한다. * q \mid p이며 p \mid (p-1)! + 1이므로 q \mid (p-1)! + 1 * q \leq (p-1)이므로 q \mid (p-1)! 즉, q는 (p-1)! + 1 과 (p-1)!의 공약수이다. (p-1)! + 1와 (p-1)!는 서로소이므로, q=1일 수밖에 없다. 즉, p는 1과 p를 제외한 양의 약수를 가지지 않으며, p는 소수이다.
# 따름정리
임의의 자연수 p>1에 대하여, 다음 두 조건이 서로 동치이다. * p는 소수이다. * (p-2)!\equiv1\pmod p
## 증명
임의의 소수 p에 대하여, :(p-2)! \equiv (p-1)! \cdot (p-1)^{-1} \equiv (p-1)! \cdot (p-1) \equiv (-1) \cdot (-1) \equiv 1 \pmod p 이다. 역의 증명도 윌슨 정리의 증명과 유사하다.
# 일반화

## 가우스의 일반화
임의의 양의 정수 n\in\mathbb Z^+에 대하여, 다음이 성립한다 (\mathbb P는 소수의 집합). :\prod_{1\le a\le n}^{\gcd\\{a,n\\}=1}a\equiv\begin{cases} -1 & n=1,2,4,p^e,2p^e,\;p\in\mathbb P\setminus\\{2\\},\;e\in\mathbb Z^+ \\\ 1 & n\ne1,2,4,p^e,2p^e,\;p\in\mathbb P\setminus\\{2\\},\;e\in\mathbb Z^+ \end{cases} \pmod n 윌슨 정리(의 필요조건 부분)은 n이 소수인 경우이다.
### 증명
n=1,2인 경우는 자명하다. n이 소수인 경우는 윌슨 정리이며, 소수의 거듭제곱인 경우의 증명은 윌슨 정리의 증명과 유사하다. 이제, n\ge3의 소인수 분해가 :n=p_1^{e_1}\cdots p_k^{e_k} 이며, k\ge2이며, :g(n)=\prod_{1\le a\le n}^{\gcd\\{a,n\\}=1}a 라고 하자. p_1^{e_1},\dots,p_k^{e_k}가 서로소이므로, 임의의 i=1,\dots,k에 대하여 :g(n)\equiv\begin{cases} -1 & n=1,2,4,p^e,2p^e,\;p\in\mathbb P\setminus\\{2\\},\;e\in\mathbb Z^+ \\\ 1 & n\ne1,2,4,p^e,2p^e,\;p\in\mathbb P\setminus\\{2\\},\;e\in\mathbb Z^+ \end{cases} \pmod{p_i^{e_i 임을 보이면 충분하다. 중국인의 나머지 정리에 따라, 다음과 같은 전단사 함수가 존재한다. (이는 군의 동형이며, 환의 동형 \mathbb Z/p_i^{e_i}\mathbb Z\times\mathbb Z/(n/p_i^{e_i})\mathbb Z\to\mathbb Z/n\mathbb Z으로부터 유도되지만, 이 사실들은 이 증명에서 사용되지 않는다.) :(\mathbb Z/p_i^{e_i}\mathbb Z)^\times\times(\mathbb Z/(n/p_i^{e_i})\mathbb Z)^\times\to(\mathbb Z/n\mathbb Z)^\times :(a_1\bmod p_i^{e_i},a_2\bmod n/p_i^{e_i})\mapsto(n/p_i^{e_i})a_1+p_i^{e_i}a_2\bmod n 따라서, 법 p_i^{e_i}에 대한 나머지를 다음과 같이 구할 수 있다. :\begin{align} g(n) & \equiv \prod_{1\le a_1\le p_i^{e_i^{\gcd\\{a_1,p_i\\}=1}\prod_{1\le a_2\le n/p_i^{e_i^{\gcd\\{a_2,n/p_i^{e_i}\\}=1}((n/p_i^{e_i})a_1+p_i^{e_i}a_2) \pmod{p_i^{e_i \\\ & \equiv \prod_{1\le a_2\le n/p_i^{e_i^{\gcd\\{a_2,n/p_i^{e_i}\\}=1}\prod_{1\le a_1\le p_i^{e_i^{\gcd\\{a_1,p_i\\}=1}(n/p_i^{e_i})a_1 \pmod{p_i^{e_i \\\ & \equiv \prod_{1\le a_2\le n/p_i^{e_i^{\gcd\\{a_2,n/p_i^{e_i}\\}=1}\prod_{1\le a_1\le p_i^{e_i^{\gcd\\{a_1,p_i\\}=1}a_1 \pmod{p_i^{e_i \\\ & \equiv g(p_i^{e_i})^{\phi(n/p_i^{e_i})} \pmod{p_i^{e_i \end{align} g(p_i^{e_i})\equiv\pm1 \pmod{p_i^{e_i인 데 주의하자. 만약 k\ge3이거나 2\nmid n이거나 4\mid n이라면, n/p_i^{e_i}\ge3이므로, \phi(n/p_i^{e_i})는 짝수이며, 따라서 :g(n) \equiv 1 \pmod{p_i^{e_i 이다. 만약 n=2p^e라면 (p는 홀수 소수, e는 양의 정수), 1 \equiv -1 \pmod 2이므로 :g(n) \equiv g(2)^{\phi(p^e)} \equiv -1 \pmod 2 이며, 또한 :g(n) \equiv g(p^e)^{\phi(2)} = g(p^e) \equiv -1 \pmod{p^e} 이다.
## 유한체
임의의 유한체 \mathbb F_q에서, 다음이 성립한다. :\prod_{a\in\mathbb F_q^\times}a=-1 윌슨 정리는 유한체의 크기가 소수 p인 경우이다. (유한체의 크기는 항상 소수의 거듭제곱이다.)
### 증명
윌슨 정리의 증명과 유사하다. \mathbb F_q의 가역원(즉, 0이 아닌 원소)들은 서로 역원인 것들끼리 짝을 지을 수 있다. 표수가 2가 아닌 경우, a^2=1은 (a-1)(a+1)=0과 동치이며, 이는 다시 a=\pm1과 동치이다. 따라서 :\prod_{a\in\mathbb F_q^\times}a=1\cdot(-1)=-1 이다. 표수가 2인 경우, a^2-1=(a-1)^2이므로, a^2=1은 a=1과 동치이며, 2=0이므로 1=-1이다. 즉, :\prod_{a\in\mathbb F_q^\times}a=1=-1 이다.