윌슨 정리

수론에서, **윌슨 정리**()는 임의의 소수 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
이다.

## 외부 링크
* 
* 
* 
* 
* 

분류:소수에 관한 정리
분류:계승과 이항식 주제
분류:모듈러 산술