윌슨 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[수론]]에서, '''윌슨 정리'''({{llang|en|Wilson's theorem}})는 임의의 [[소수 (수론)|소수]] <math>p</math>에 대하여, <math>p-1</math>의 [[계승 (수학)|계승]]이 법 <math>p</math>에 대하여 −1과 [[합동 (대수학)|합동]]이라는 정리이다.

== 정의 ==
'''윌슨 정리'''에 따르면, 임의의 자연수 <math>p>1</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>p</math>는 [[소수 (수론)|소수]]이다.
* <math>(p-1)!\equiv-1\pmod p</math>
여기서 <math>!</math>는 [[계승 (수학)|계승]]이며, <math>\equiv\pmod p</math>는 법 <math>p</math>에 대한 [[합동 (대수학)|합동]]이다. 두 번째 조건은 [[약수]] 관계를 사용하여
:<math>p\mid(p-1)!+1</math>
로 바꿔 쓸 수 있다. 나머지의 개념을 사용하면, <math>(p-1)!</math>를 <math>p</math>로 나눈 나머지가 <math>p-1</math>이라고 바꿔 말할 수 있다.

윌슨 정리는 <math>p>1</math>가 소수일 [[필요충분조건]]을 제시한다. 물론, 계승의 계산은 오래 걸리므로 충분조건 부분을 통해 소수를 판별하는 것은 매우 느리다.

== 증명 ==
=== 필요조건의 증명 ===
<math>p=2</math>인 경우는 자명하다. 만약 <math>p</math>가 3 이상의 소수라면, 법 <math>p</math>에 대한 합동류들로 구성된 [[가환환]] <math>\mathbb Z/p\mathbb Z</math>는 [[체 (수학)|체]]를 이룬다. 즉, 임의의 <math>i=1,\dots,p-1</math>에 대하여,
:<math>ii^{-1}\equiv1\pmod p</math>
인 <math>i^{-1}=1,\dots,p-1</math>가 존재한다. <math>i^{-1}</math>는 <math>i</math>의 법 <math>p</math>에 대한 곱셈 역원이다. 역원은 유일하며, 역원의 역원은 스스로와 같다. 따라서, 정수 <math>1,\dots,p-1</math>들을 서로 역원인 것들끼리 짝을 지을 수 있다. 다만, 스스로의 역원인 것들은 혼자 짝을 이룬다. 스스로의 역원인 조건 <math>i=i^{-1}</math>은 곧 조건
:<math>i^2\equiv1\pmod p</math>
와 같다. 이는 양변에서 1을 빼 얻는 조건
:<math>(i-1)(i+1)\equiv0\pmod p</math>
와 동치이다. <math>\mathbb Z/p\mathbb Z</math>가 [[정역]]이므로, 이는 다시
:<math>i-1\equiv0\pmod p</math>
이거나
:<math>i+1\equiv0\pmod p</math>
인 것과 동치이다. <math>i=1,\dots,p-1</math>이므로, 전자는 <math>i=1</math>이며, 후자는 <math>i=p-1</math>이다. 이제 모든 <math>1,\dots,p-1</math>의 곱을 생각하자. 1과 <math>p-1</math>을 제외한 것들은 역원끼리 짝을 지어 곱하면 1과 합동이 되므로, 1과 <math>p-1</math>만 남는다. 즉,
:<math>(p-1)! \equiv 1\cdot(p-1) \equiv -1 \pmod p</math>
이다.

예를 들어, <math>p=11</math>인 경우
:<math>10! = 1\cdot10\cdot(2 \cdot 6)\cdot(3 \cdot 4)\cdot(5 \cdot 9)\cdot(7 \cdot 8) \equiv -1 \pmod{11}</math>
이다.

=== 충분조건의 증명 ===
이제 <math>p>1</math>이 1보다 큰 양의 정수이며,
:<math>(p-1)! \equiv -1 \pmod p</math>
이며, <math>q</math>가 <math>1\le q\le p-1</math>인 <math>p</math>의 약수라고 가정하자. 그렇다면 다음이 성립한다.
* <math>q \mid p</math>이며 <math>p \mid (p-1)! + 1</math>이므로 <math>q \mid (p-1)! + 1</math>
* <math>q \leq (p-1)</math>이므로 <math>q \mid (p-1)!</math>
즉, <math>q</math>는 <math>(p-1)! + 1</math> 과 <math>(p-1)!</math>의 공약수이다. <math>(p-1)! + 1</math>와 <math>(p-1)!</math>는 서로소이므로, <math>q=1</math>일 수밖에 없다. 즉, <math>p</math>는 1과 <math>p</math>를 제외한 양의 약수를 가지지 않으며, <math>p</math>는 소수이다.

== 따름정리 ==
임의의 자연수 <math>p>1</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>p</math>는 [[소수 (수론)|소수]]이다.
* <math>(p-2)!\equiv1\pmod p</math>

=== 증명 ===
임의의 소수 <math>p</math>에 대하여,
:<math>(p-2)! \equiv (p-1)! \cdot (p-1)^{-1} \equiv (p-1)! \cdot (p-1) \equiv (-1) \cdot (-1) \equiv 1 \pmod p</math>
이다. 역의 증명도 윌슨 정리의 증명과 유사하다.

== 일반화 ==
=== 가우스의 일반화 ===
임의의 양의 정수 <math>n\in\mathbb Z^+</math>에 대하여, 다음이 성립한다 (<math>\mathbb P</math>는 소수의 집합).
:<math>\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
</math>

윌슨 정리(의 필요조건 부분)은 <math>n</math>이 소수인 경우이다.

==== 증명 ====
<math>n=1,2</math>인 경우는 자명하다. <math>n</math>이 소수의 거듭제곱인 경우의 증명은 윌슨 정리의 증명과 유사하다. 이제, <math>n\ge3</math>의 소인수 분해가
:<math>n=p_1^{e_1}\cdots p_k^{e_k}</math>
이며, <math>k\ge2</math>이며,
:<math>g(n)=\prod_{1\le a\le n}^{\gcd\{a,n\}=1}a</math>
라고 하자. [[중국인의 나머지 정리]]에 따라, 임의의 <math>i=1,\dots,k</math>에 대하여
:<math>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}}
</math>
임을 보이면 충분하다.

다음과 같은 전단사 함수가 존재한다. (이는 군의 동형이며, 환의 동형 <math>\mathbb Z/p_i^{e_i}\mathbb Z\times\mathbb Z/(n/p_i^{e_i})\mathbb Z\to\mathbb Z/n\mathbb Z</math>으로부터 유도되지만, 이 사실들은 이 증명에서 사용되지 않는다.)
:<math>(\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</math>
:<math>(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</math>

따라서, 법 <math>p_i^{e_i}</math>에 대한 나머지를 다음과 같이 구할 수 있다.
:<math>\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}
</math>
마지막 <math>g(p_i^{e_i})^{\phi(n/p_i^{e_i})}</math>는 <math>\pm1</math>을 값으로 한다. 만약 <math>p_1,\dots,p_n\ne2</math>라면, 모든 <math>i</math>에 대하여, (<math>n/p_i^{e_i}\ge3</math>이므로) <math>\phi(n/p_i^{e_i})</math>는 짝수이며, 따라서
:<math>g(n) \equiv 1 \pmod{p_i^{e_i}}</math>
이다. 만약 <math>p_1=2</math>이며 <math>k\ge3</math>이라면, 역시 모든 <math>i</math>에 대하여 <math>\phi(n/p_i^{e_i})</math>는 짝수이므로
:<math>g(n) \equiv 1 \pmod{p_i^{e_i}}</math>
이다. 만약 <math>p_1=2</math>이며 <math>k=2</math>이며 <math>e_1\ge2</math>라면, 역시 모든 <math>i</math>에 대하여 <math>\phi(n/p_i^{e_i})</math>는 짝수이므로
:<math>g(n) \equiv 1 \pmod{p_i^{e_i}}</math>
이다. 만약 <math>p_1=2</math>이며 <math>k=2</math>이며 <math>e_1=1</math>이라면,
:<math>1 \equiv -1 \pmod 2</math>
이므로
:<math>g(n) \equiv -1 \pmod 2</math>
이며, 또한
:<math>g(n) \equiv g(p_2^{e_2})^{\phi(2)} = g(p_2^{e_2}) \equiv -1 \pmod{p_2^{e_2}}</math>
이다.

=== 유한체 ===
임의의 [[유한체]] <math>\mathbb F_q</math>에서, 다음이 성립한다.
:<math>\prod_{a\in\mathbb F_q^\times}a=-1</math>
윌슨 정리는 유한체의 크기가 소수 <math>p</math>인 경우이다. (유한체의 크기는 항상 소수의 거듭제곱이다.)

==== 증명 ====
윌슨 정리의 증명과 유사하다. <math>\mathbb F_q</math>의 [[가역원]](즉, 0이 아닌 원소)들은 서로 역원인 것들끼리 짝을 지을 수 있다. [[환의 표수|표수]]가 2가 아닌 경우, <math>a^2=1</math>은 <math>(a-1)(a+1)=0</math>과 동치이며, 이는 다시 <math>a=\pm1</math>과 동치이다. 따라서
:<math>\prod_{a\in\mathbb F_q^\times}a=1\cdot(-1)=-1</math>
이다. 표수가 2인 경우, <math>a^2-1=(a-1)^2</math>이므로, <math>a^2=1</math>은 <math>a=1</math>과 동치이며, <math>2=0</math>이므로 <math>1=-1</math>이다. 즉,
:<math>\prod_{a\in\mathbb F_q^\times}=1=-1</math>
이다.

== 외부 링크 ==
* {{수학노트|제목=윌슨의 정리}}
* {{eom|제목=Wilson theorem}}
* {{매스월드|id=WilsonsTheorem|제목=Wilson’s theorem}}
* {{플래닛매스|urlname=WilsonsTheorem|제목=Wilson’s theorem}}
* {{플래닛매스|urlname=proofofwilsonstheorem|제목=Proof of Wilson’s theorem}}

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