윌슨의 정리

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

$(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)\}}$는 $p$에 대한 가환환을 이룬다.

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

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

${\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}$을 제외한 원소들을 모두 곱하면 법 $p$에 대해 1과 합동이 되고, ${\textstyle G}$의 원소들을 모두 곱한 값, 즉 ${\textstyle (p-1)!}$의 값은 −1과 합동이 된다.

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

$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}}}$가 된다.

$\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. $q|p$ 이며 ${\textstyle p\ |(p-1)!+1}$이므로 $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}$는 모두 소수임을 알 수 있다.

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

따름 정리

임의의 소수 $p$에 대해

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