📂정수론

윌슨의 정리 증명

정리 ¹

2보다 큰 소수 $p$ 에 대해, $(p-1)! \equiv -1 \pmod{p}$

설명

페르마의 소정리만큼은 아니더라도, 윌슨의 정리 역시 여기저기서 유용하게 쓰인다. 생긴 모양새부터가 연속되는 수들의 곱을 계산할 때 편리하게 생겼다.

증명

$\pmod{p}$ 에서 곱셈에 대한 역원의 존재성, 유일성을 이용한 증명1과 원시근Primitive root의 성질, 페르마의 소정리를 이용한 증명2 두가지를 소개한다. 증명2가 조금 더 어렵지만 조금 더 세련됐다. 취향에 맞는 증명을 숙지하도록 하자.

원시근의 성질을 이용한 증명 1

$i$가 1보다 크고 $(p-1)$보다 작은 정수라고 하면 $(p-1)!$ 을 아래와 같이 나타낼 수 있다. $$(p-1)! = 1 \cdot 2 \cdot 3 \cdots i \cdots (p-2) \cdot (p-1)$$

합동식에서 곱셈에 대한 역원: 정수환 $\mathbb{Z}_{p}$는 $p$ 가 소수면 정수체다. 다시 말해, $\gcd(p,a) = 1$ 면 방정식 $a x \equiv 1 \pmod{p}$ 는 $0<x<p$에서 단 하나의 해를 가진다.

정수는 $\pmod{p}$ 에서 반드시 역원을 단 하나 가지므로, $1$ 과 $(p-1)$ 을 제외한 모든 정수들은 다른 어떤 정수과 곱해져서 $1$ 이 될 것이다. $p$가 짝수가 아닌 소수기 때문에 이러한 $i$ 는 정확히 짝수개만큼 존재하며,결국 남는 것은 $$(p-1)! \equiv 1 \cdot 1 \cdot 1 \cdots 1 \cdot (p-1) \pmod{p}$$ 이다. $(p-1) \equiv -1 \pmod{p}$ 이므로, $(p-1)! \equiv -1 \pmod{p}$ 이 성립한다.

■

예를 들어 $(7-1)! \equiv 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \pmod{7}$ 을 보면 $$2 \cdot 4 \equiv 8 \equiv 1 \pmod{7} \\ 3 \cdot 5 \equiv 15 \equiv 1 \pmod{7}$$ 이므로 $$(7-1)! \equiv 1 \cdot 1 \cdot 1 \cdot 6 \equiv 6 \equiv -1 \pmod{7}$$ 이 된다. 조금 더 큰 소수 몇개를 직접 손으로 계산해보면 확실히 감이 잡힐 것이다.

페르마의 소정리를 이용한 증명 2

$a$를 소수 $p$ 의 원시근라고 하면 $(p-1)!$ 을 아래와 같이 나타낼 수 있다.

$$\begin{align*} (p-1)! & \equiv 1 \cdot 2 \cdot 3 \cdots (p-2) \cdot (p-1) \pmod{p} \\ & \equiv a^{1} \cdot a^{2} \cdot a^{3} \cdots a^{p-2} \cdot a^{p-1} \pmod{p} \\ & \equiv a^{{p(p-1)} \over {2}} \pmod{p} \\ & \equiv a^{ { {p-1} \over 2 } p } \pmod{p} \end{align*}$$

페르마의 소정리: $a^{p-1} \equiv 1 \pmod{p}$

$a$ 는 $p$ 의 원시근이므로 페르마의 소정리에 의해 $a^{ { {p-1} \over 2 } p } \equiv (-1)^p \pmod{p}$ 이 성립한다. 한편 $p$ 는 2보다 큰 소수이므로 홀수고, 따라서 다음을 얻는다. $$(p-1)! \equiv (-1)^p \equiv -1 \pmod{p}$$

■