윌슨의 정리

윌슨의 정리란 1보다 큰 소수 $p$에 대해

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

가 성립하는 것을 말한다. 증명하기 전에 한가지 알고 가야 할 것이 있다.

 

위수

1 이상의 정수 m에 대해 $gcd(a,m)=1$일 때

$a^{n} \equiv 1 \pmod{m}$

가 성립하는 최소의 자연수 $n$을 법 $m$에 대한 $a$의 위수라고 하고 $e_{m}(a)$ 로 정의한다.

 

<증명>

보조정리를 활용하면 다음을 알 수 있다.

$\left\{a,a^{2}, ..., a^{p-1} \right\} \equiv \left\{1,2, ... , p-1 \right\} \pmod{p}$

왼쪽의 집합과 오른쪽의 집합의 원소를 모두 곱하자.

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

페르마 소정리에 의해

$a^{\frac{p-1}{2}} \equiv (p-1)! \pmod{p}$

페르마 소정리에 의해

$a^{p-1} \equiv 1\pmod{p}$

$a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}$

위수의 가정에 의해

$a^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

따라서 다음을 얻는다.

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

$\blacksquare$

 

보조정리

임의의 소수 $p$에 대해 $e_{p}(a)=p-1$ 일 때 집합 $\left\{a, a^{2} , ... , a^{p-1} \right\} \pmod{p}$ 의 모든 원소는 다르다.

<증명(귀류법)>

$1 \le i < j \le p-1$인 임의의 정수 i, j에 대해

$a^{j} \equiv a^{i} \pmod{p}$

가 성립한다고 하자.

$a^{j-i} \equiv 1 \pmod{p}$

반면 $j-i<p-1$ 이므로 가정에 어긋난다. 따라서 모순이다.

 

 

 # 2021-08-24 추가됨

윌슨의 정리에 대한 또 다른 증명법을 찾아내 소개한다.

 

<증명 1>

임의의 소수 $p$에 대하여 $p$의 기약잉여계는 1부터 $p-1$까지의 원소를 포함한다.

이 원소들 중 임의의 원소를 $m$이라 하자. 그때 $m$의 역원을 $m^{\prime}$이라 하자.

$mm^{\prime} \equiv 1 \pmod{p}$

$mm^{\prime}=np+1$

$mm^{\prime}-np=1$

이때 $\gcd(m,p)=1$이므로  

$mm^{\prime}-np=\gcd(m,p)$

이다. 위 식을보면 베주 항등식의 꼴을 만족한다는 것을 알 수 있으며 조건을 만족하는 정수해 $m^{\prime}$과 $n$이 존재함을 알 수 있다. 이렇게 튀어나온 $m^{\prime}$은 법 $p$에 대해 합동이기 때문에 곱에 대한 역원이 기약잉여계에 속함을 알 수 있다. 이제 기약잉여계의 서로 다른 원소 $a,b$($ab \not\equiv 1 \pmod{p}$)에 대해 역원이 서로 다름을 보이면 된다. 마찬가지로 각 역원을 $a^{\prime}, b^{\prime}$라고 하면

$aa^{\prime} \equiv bb^{\prime} \pmod{p}$

이때 다음을 가정하자.

$a^{\prime} \equiv b^{\prime} \pmod{p}$

$\gcd(a^{\prime},p)=1$($b^{\prime}$도 마찬가지이다.)이므로 양변을 $a^{\prime}$으로 나눠주면

$a \equiv b \pmod{p}$

이는 첫 가정과 모순이므로 귀류법에 의해 

$a^{\prime} \not\equiv b^{\prime} \pmod{p}$

따라서 $p-1$개의 수들은 각각 곱이 1과 합동이 되는 짝꿍이 있음을 알 수 있다. 하지만 1, $p-1$은 자기 자신과의 곱이 1로 합동이므로 이 두 수를 제외하자. 그럼 나머지 수들의 곱은 1과 합동이고 마지막으로 1과 $p-1$을 곱해주면 

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

를 얻는다.

 

<증명 2>

가장 처음 증명법에서 사용했던 보조정리를 살펴보자.

$\left\{a, a^{2} , ... , a^{p-1} \right\} (mod\ p)$

사실 이 집합에는 더 놀라운 성질이 있다.

$aa^{p-2} \equiv 1 \pmod{p}$

$a^{2}a^{p-3} \equiv 1 \pmod{p}$

...

아마 여러분도 알아챘을 것이다. 

이 방식으로 집합의 모든 원소를 곱하면 최종적으로 남는 것은

$(p-1)! \equiv a^{(p-1)/2} \pmod{p}$

위수의 정의에 의해

$a^{(p-1)/2} \equiv -1 \pmod{p}$

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