윌슨의 정리

윌슨의 정리(영어: Wilson's Theorem)는 1 보다 큰 자연수 ${\textstyle p}$에 대해서

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

위 명제가 성립함은 ${\textstyle p}$가 소수일 필요충분조건이라는 정수론의 정리이다.

즉, 자연수 ${\textstyle p>1}$에 대해 다음 두 명제가 성립한다:

• ${\textstyle p}$가 소수이면 ${\textstyle p\ |\ (p-1)!+1}$
• ${\textstyle p\ |\ (p-1)!+1}$가 성립하면 ${\textstyle p}$는 소수

증명

필요조건의 증명

만약 ${\textstyle p}$가 소수이면, ${\textstyle p}$의 기약잉여계 ${\textstyle G=(\mathbb {Z} /p\mathbb {Z} )^{\times }\equiv \{1,2,3,\ldots ,(p-1)\}}$는 ${\displaystyle p}$에 대한 가환환을 이룬다.

이것은 ${\textstyle G}$의 임의의 원소 ${\displaystyle i}$에 대하여, ${\textstyle ij\equiv 1{\pmod {p}}}$이 성립하는 역원 ${\textstyle j}$가 존재한다는 것이다.

만약 ${\textstyle i\equiv j{\pmod {p}}}$이면,

${\displaystyle {\begin{alignedat}{2}i^{2}\equiv 1{\pmod {p}}&\Longrightarrow \ i^{2}-1\equiv (i-1)(i+1)\equiv 0{\pmod {p}}\\&\Longrightarrow i\equiv 1\ \mathrm {or} \ (p-1)\\\end{alignedat}}}$

이와 같이 ${\textstyle 1}$ 과 ${\textstyle p-1}$만이 자기 자신을 곱의 역원으로 가지고, 나머지 원소들은 자신이 아닌 다른 원소를 역원으로 갖는다.

따라서, ${\textstyle 1}$ 과 ${\textstyle p-1}$을 제외한 원소들을 모두 곱하면 법 ${\displaystyle p}$에 대해 1과 합동이 되고, ${\textstyle G}$의 원소들을 모두 곱한 값, 즉 ${\textstyle (p-1)!}$의 값은 −1과 합동이 된다.

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

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

로 성립하며, ${\textstyle p=2}$인 경우 ${\textstyle (2-1)!=1\equiv -1{\pmod {2}}}$가 된다.

${\displaystyle \therefore p\in \mathbb {P} \ \Longrightarrow (p-1)!\equiv 1{\pmod {p}}}$ (단, ${\textstyle \mathbb {P} }$는 소수들의 집합)

충분조건의 증명

${\textstyle (p-1)!\ \equiv \ -1{\pmod {p}}}$인 ${\textstyle p}$ 중 합성수인 ${\textstyle p}$가 존재한다고 가정하자.

${\textstyle p}$가 합성수이면 ${\textstyle 1<q\leq p-1}$인 ${\textstyle p}$의 약수 ${\textstyle q}$를 잡을 수 있다.

1. ${\displaystyle q|p}$이며 ${\textstyle p\ |(p-1)!+1}$이므로 ${\displaystyle q\ |(p-1)!+1}$
2. ${\textstyle q\leq (p-1)}$이므로 ${\textstyle q\ |(p-1)!}$

즉, ${\textstyle q}$는 ${\textstyle (p-1)!+1}$ 과 ${\textstyle (p-1)!}$의 공약수인데,

이는 ${\textstyle (p-1)!+1}$ 와 ${\textstyle (p-1)!}$는 서로소임에 모순된다.

따라서 귀류법을 통해 조건을 만족하는 ${\textstyle p}$는 모두 소수임을 알 수 있다.

${\displaystyle \therefore (p-1)!\equiv 1{\pmod {p}}\ \Longrightarrow p\in \mathbb {P} }$ (단, ${\textstyle \mathbb {P} }$는 소수들의 집합)

따름 정리

임의의 소수 ${\displaystyle p}$에 대해

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