윌슨 정리

틀:위키데이터 속성 추적 수론에서, 윌슨 정리(틀:Llang)는 임의의 소수 $p$에 대하여, $p-1$의 계승이 법 $p$에 대하여 −1과 합동이라는 정리이다.

정의

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

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

여기서 $!$는 계승이며, $\equiv (\mathrm{mod}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$에 대하여,

$i{i}^{-1}\equiv 1(\mathrm{mod}p)$

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

$i^2\equiv 1(\mathrm{mod}p)$

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

$(i-1)(i+1)\equiv 0(\mathrm{mod}p)$

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

$i-1\equiv 0(\mathrm{mod}p)$

이거나

$i+1\equiv 0(\mathrm{mod}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(\mathrm{mod}p)$

이다.

예를 들어, $p=11$인 경우

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

이다.

충분조건의 증명

이제 $p>1$이 1보다 큰 양의 정수이며,

$(p-1)!\equiv -1(\mathrm{mod}p)$

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

• $q\mid p$이며 $p\mid (p-1)!+1$이므로 $q\mid (p-1)!+1$
• $q\le (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)!\equiv 1(\mathrm{mod}p)$

증명

임의의 소수 $p$에 대하여,

$(p-2)!\equiv (p-1)!\cdot (p-1{)}^{-1}\equiv (p-1)!\cdot (p-1)\equiv (-1)\cdot (-1)\equiv 1(\mathrm{mod}p)$

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

일반화

가우스의 일반화

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

$\prod _{1\le a\le n}^{\gcd \{a,n\}=1}a\equiv \{\begin{array}{cc}-1& n=1,2,4,p^e,2p^e,p\in \mathbb{P}\setminus \{2\},e\in {\mathbb{Z}}^{+}\\ 1& n\ne 1,2,4,p^e,2p^e,p\in \mathbb{P}\setminus \{2\},e\in {\mathbb{Z}}^{+}\end{array}(\mathrm{mod}n)$

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

증명

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

$n=p_1^{e_1}\cdots p_k^{e_k}$

이며, $k\ge 2$이며,

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

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

$g(n)\equiv \{\begin{array}{cc}-1& n=1,2,4,p^e,2p^e,p\in \mathbb{P}\setminus \{2\},e\in {\mathbb{Z}}^{+}\\ 1& n\ne 1,2,4,p^e,2p^e,p\in \mathbb{P}\setminus \{2\},e\in {\mathbb{Z}}^{+}\end{array}(\mathrm{mod}{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{modp}_i^{e_i},a_{2}modn/p_i^{e_i})\mapsto (n/p_i^{e_i})a_1+p_i^{e_i}{a}_{2}modn$

따라서, 법 $p_i^{e_i}$에 대한 나머지를 다음과 같이 구할 수 있다.

$\begin{array}{cc}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)(\mathrm{mod}{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(\mathrm{mod}{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(\mathrm{mod}{p}_i^{e_i})\\ & \equiv g(p_i^{e_i}{)}^{\varphi (n/p_i^{e_i})}(\mathrm{mod}{p}_i^{e_i})\end{array}$

마지막 $g(p_i^{e_i}{)}^{\varphi (n/p_i^{e_i})}$는 $\pm 1$을 값으로 한다. 만약 $p_1,\dots ,p_n\ne 2$라면, 모든 $i$에 대하여, ($n/p_i^{e_i}\ge 3$이므로) $\varphi (n/p_i^{e_i})$는 짝수이며, 따라서

$g(n)\equiv 1(\mathrm{mod}{p}_i^{e_i})$

이다. 만약 $p_1=2$이며 $k\ge 3$이라면, 역시 모든 $i$에 대하여 $\varphi (n/p_i^{e_i})$는 짝수이므로

$g(n)\equiv 1(\mathrm{mod}{p}_i^{e_i})$

이다. 만약 $p_1=2$이며 $k=2$이며 $e_1\ge 2$라면, 역시 모든 $i$에 대하여 $\varphi (n/p_i^{e_i})$는 짝수이므로

$g(n)\equiv 1(\mathrm{mod}{p}_i^{e_i})$

이다. 만약 $p_1=2$이며 $k=2$이며 $e_1=1$이라면,

$1\equiv -1(\mathrm{mod}2)$

이므로

$g(n)\equiv -1(\mathrm{mod}2)$

이며, 또한

$g(n)\equiv g(p_2^{e_2}{)}^{\varphi (2)}=g(p_2^{e_2})\equiv -1(\mathrm{mod}{p}_2^{e_2})$

이다.

유한체

임의의 유한체 ${𝔽}_q$에서, 다음이 성립한다.

$\prod _{a\in {𝔽}_q^{\times }}a=-1$

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

증명

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

$\prod _{a\in {𝔽}_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 {𝔽}_q^{\times }}=1=-1$

이다.

외부 링크

• 틀:수학노트
• 틀:Eom
• 틀:매스월드
• 틀:플래닛매스
• 틀:플래닛매스