윌슨 정리

수론에서, 윌슨 정리(영어: Wilson's theorem)는 임의의 소수 ${\displaystyle p}$에 대하여, ${\displaystyle p-1}$의 계승이 법 ${\displaystyle p}$에 대하여 −1과 합동이라는 정리이다.

정의

윌슨 정리에 따르면, 임의의 자연수 ${\displaystyle p>1}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle p}$는 소수이다.
• ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

여기서 ${\displaystyle$ !} 는 계승이며, ${\displaystyle \equiv {\pmod {p}}}$는 법 ${\displaystyle p}$에 대한 합동이다. 두 번째 조건은 약수 관계를 사용하여

${\displaystyle p\mid (p-1)!+1}$

로 바꿔 쓸 수 있다. 나머지의 개념을 사용하면, ${\displaystyle (p-1)!}$를 ${\displaystyle p}$로 나눈 나머지가 ${\displaystyle p-1}$이라고 바꿔 말할 수 있다.

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

증명

필요조건의 증명

${\displaystyle p=2}$인 경우는 자명하다. 만약 ${\displaystyle p}$가 3 이상의 소수라면, 법 ${\displaystyle p}$에 대한 합동류들로 구성된 가환환 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$는 체를 이룬다. 즉, 임의의 ${\displaystyle i=1,\dots ,p-1}$에 대하여,

${\displaystyle ii^{-1}\equiv 1{\pmod {p}}}$

인 ${\displaystyle i^{-1}=1,\dots ,p-1}$가 존재한다. ${\displaystyle i^{-1}}$는 ${\displaystyle i}$의 법 ${\displaystyle p}$에 대한 곱셈 역원이다. 역원은 유일하며, 역원의 역원은 스스로와 같다. 따라서, 정수 ${\displaystyle 1,\dots ,p-1}$들을 서로 역원인 것들끼리 짝을 지을 수 있다. 다만, 스스로의 역원인 것들은 혼자 짝을 이룬다. 스스로의 역원인 조건 ${\displaystyle i=i^{-1}}$은 곧 조건

${\displaystyle i^{2}\equiv 1{\pmod {p}}}$

와 같다. 이는 양변에서 1을 빼 얻는 조건

${\displaystyle (i-1)(i+1)\equiv 0{\pmod {p}}}$

와 동치이다. ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$가 정역이므로, 이는 다시

${\displaystyle i-1\equiv 0{\pmod {p}}}$

이거나

${\displaystyle i+1\equiv 0{\pmod {p}}}$

인 것과 동치이다. ${\displaystyle i=1,\dots ,p-1}$이므로, 전자는 ${\displaystyle i=1}$이며, 후자는 ${\displaystyle i=p-1}$이다. 이제 모든 ${\displaystyle 1,\dots ,p-1}$의 곱을 생각하자. 1과 ${\displaystyle p-1}$을 제외한 것들은 역원끼리 짝을 지어 곱하면 1과 합동이 되므로, 1과 ${\displaystyle p-1}$만 남는다. 즉,

${\displaystyle (p-1)!\equiv 1\cdot (p-1)\equiv -1{\pmod {p}}}$

이다.

예를 들어, ${\displaystyle p=11}$인 경우

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

이다.

충분조건의 증명

이제 ${\displaystyle p>1}$이 1보다 큰 양의 정수이며,

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

이며, ${\displaystyle q}$가 ${\displaystyle 1\leq q\leq p-1}$인 ${\displaystyle p}$의 약수라고 가정하자. 그렇다면 다음이 성립한다.

• ${\displaystyle q\mid p}$이며 ${\displaystyle p\mid (p-1)!+1}$이므로 ${\displaystyle q\mid (p-1)!+1}$
• ${\displaystyle q\leq (p-1)}$이므로 ${\displaystyle q\mid (p-1)!}$

즉, ${\displaystyle q}$는 ${\displaystyle (p-1)!+1}$ 과 ${\displaystyle (p-1)!}$의 공약수이다. ${\displaystyle (p-1)!+1}$와 ${\displaystyle (p-1)!}$는 서로소이므로, ${\displaystyle q=1}$일 수밖에 없다. 즉, ${\displaystyle p}$는 1과 ${\displaystyle p}$를 제외한 양의 약수를 가지지 않으며, ${\displaystyle p}$는 소수이다.

따름정리

임의의 자연수 ${\displaystyle p>1}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle p}$는 소수이다.
• ${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$

증명

임의의 소수 ${\displaystyle p}$에 대하여,

${\displaystyle (p-2)!\equiv (p-1)!\cdot (p-1)^{-1}\equiv (p-1)!\cdot (p-1)\equiv (-1)\cdot (-1)\equiv 1{\pmod {p}}}$

이다. 역의 증명도 윌슨 정리의 증명과 유사하다.

일반화

가우스의 일반화

임의의 양의 정수 ${\displaystyle n\in \mathbb {Z} ^{+}}$에 대하여, 다음이 성립한다 (${\displaystyle \mathbb {P} }$는 소수의 집합).

${\displaystyle \prod _{1\leq a\leq 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\neq 1,2,4,p^{e},2p^{e},\;p\in \mathbb {P} \setminus \{2\},\;e\in \mathbb {Z} ^{+}\end{cases}}{\pmod {n}}}$

윌슨 정리(의 필요조건 부분)은 ${\displaystyle n}$이 소수인 경우이다.

증명

${\displaystyle n=1,2}$인 경우는 자명하다. ${\displaystyle n}$이 소수의 거듭제곱인 경우의 증명은 윌슨 정리의 증명과 유사하다. 이제, ${\displaystyle n\geq 3}$의 소인수 분해가

${\displaystyle n=p_{1}^{e_{1}}\cdots p_{k}^{e_{k}}}$

이며, ${\displaystyle k\geq 2}$이며,

${\displaystyle g(n)=\prod _{1\leq a\leq n}^{\gcd\{a,n\}=1}a}$

라고 하자. 중국인의 나머지 정리에 따라, 임의의 ${\displaystyle i=1,\dots ,k}$에 대하여

${\displaystyle 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\neq 1,2,4,p^{e},2p^{e},\;p\in \mathbb {P} \setminus \{2\},\;e\in \mathbb {Z} ^{+}\end{cases}}{\pmod {p_{i}^{e_{i}}}}}$

임을 보이면 충분하다.

다음과 같은 전단사 함수가 존재한다. (이는 군의 동형이며, 환의 동형 ${\displaystyle \mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} \times \mathbb {Z} /(n/p_{i}^{e_{i}})\mathbb {Z} \to \mathbb {Z} /n\mathbb {Z} }$으로부터 유도되지만, 이 사실들은 이 증명에서 사용되지 않는다.)

${\displaystyle (\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 }}$

${\displaystyle (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}}}$

따라서, 법 ${\displaystyle p_{i}^{e_{i}}}$에 대한 나머지를 다음과 같이 구할 수 있다.

${\displaystyle {\begin{aligned}g(n)&\equiv \prod _{1\leq a_{1}\leq p_{i}^{e_{i}}}^{\gcd\{a_{1},p_{i}\}=1}\prod _{1\leq a_{2}\leq 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\leq a_{2}\leq n/p_{i}^{e_{i}}}^{\gcd\{a_{2},n/p_{i}^{e_{i}}\}=1}\prod _{1\leq a_{1}\leq 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\leq a_{2}\leq n/p_{i}^{e_{i}}}^{\gcd\{a_{2},n/p_{i}^{e_{i}}\}=1}\prod _{1\leq a_{1}\leq 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{aligned}}}$

마지막 ${\displaystyle g(p_{i}^{e_{i}})^{\phi (n/p_{i}^{e_{i}})}}$는 ${\displaystyle \pm 1}$을 값으로 한다. 만약 ${\displaystyle p_{1},\dots ,p_{n}\neq 2}$라면, 모든 ${\displaystyle i}$에 대하여, (${\displaystyle n/p_{i}^{e_{i}}\geq 3}$이므로) ${\displaystyle \phi (n/p_{i}^{e_{i}})}$는 짝수이며, 따라서

${\displaystyle g(n)\equiv 1{\pmod {p_{i}^{e_{i}}}}}$

이다. 만약 ${\displaystyle p_{1}=2}$이며 ${\displaystyle k\geq 3}$이라면, 역시 모든 ${\displaystyle i}$에 대하여 ${\displaystyle \phi (n/p_{i}^{e_{i}})}$는 짝수이므로

${\displaystyle g(n)\equiv 1{\pmod {p_{i}^{e_{i}}}}}$

이다. 만약 ${\displaystyle p_{1}=2}$이며 ${\displaystyle k=2}$이며 ${\displaystyle e_{1}\geq 2}$라면, 역시 모든 ${\displaystyle i}$에 대하여 ${\displaystyle \phi (n/p_{i}^{e_{i}})}$는 짝수이므로

${\displaystyle g(n)\equiv 1{\pmod {p_{i}^{e_{i}}}}}$

이다. 만약 ${\displaystyle p_{1}=2}$이며 ${\displaystyle k=2}$이며 ${\displaystyle e_{1}=1}$이라면,

${\displaystyle 1\equiv -1{\pmod {2}}}$

이므로

${\displaystyle g(n)\equiv -1{\pmod {2}}}$

이며, 또한

${\displaystyle g(n)\equiv g(p_{2}^{e_{2}})^{\phi (2)}=g(p_{2}^{e_{2}})\equiv -1{\pmod {p_{2}^{e_{2}}}}}$

이다.

유한체

임의의 유한체 ${\displaystyle \mathbb {F} _{q}}$에서, 다음이 성립한다.

${\displaystyle \prod _{a\in \mathbb {F} _{q}^{\times }}a=-1}$

윌슨 정리는 유한체의 크기가 소수 ${\displaystyle p}$인 경우이다. (유한체의 크기는 항상 소수의 거듭제곱이다.)

증명

윌슨 정리의 증명과 유사하다. ${\displaystyle \mathbb {F} _{q}}$의 가역원(즉, 0이 아닌 원소)들은 서로 역원인 것들끼리 짝을 지을 수 있다. 표수가 2가 아닌 경우, ${\displaystyle a^{2}=1}$은 ${\displaystyle (a-1)(a+1)=0}$과 동치이며, 이는 다시 ${\displaystyle a=\pm 1}$과 동치이다. 따라서

${\displaystyle \prod _{a\in \mathbb {F} _{q}^{\times }}a=1\cdot (-1)=-1}$

이다. 표수가 2인 경우, ${\displaystyle a^{2}-1=(a-1)^{2}}$이므로, ${\displaystyle a^{2}=1}$은 ${\displaystyle a=1}$과 동치이며, ${\displaystyle 2=0}$이므로 ${\displaystyle 1=-1}$이다. 즉,

${\displaystyle \prod _{a\in \mathbb {F} _{q}^{\times }}=1=-1}$

이다.

외부 링크

• 이철희. “윌슨의 정리”. 《수학노트》.
• “Wilson theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
• Weisstein, Eric Wolfgang. “Wilson’s theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• “Wilson’s theorem”. 《PlanetMath》 (영어).
• “Proof of Wilson’s theorem”. 《PlanetMath》 (영어).