Number Theory - 5.3 윌슨의 정리

정수론 4대 정리는 다음과 같다.

1. 페르마 정리
2. 중국인의 나머지 정리
3. 윌슨의 정리
4. 오일러 정리

그 중 하나인 윌슨의 정리에 대해 정리해보자.

---

윌슨의 정리

Theorem 5.4 윌슨의 정리

$p$가 소수이면 $(p-1)! \equiv -1 \pmod p$

증명

$p=2, p=3$ 인 경우는 분명하므로 $p>3$ 이라 하자.

$a$를 $p-1$ 개의 양의 정수 $1,2,3,\dots,p-1$ 중 하나라 가정하고, $ax \equiv 1 \pmod p$ 를 생각하자.

$gcd(a,p)=1$ 이므로 Theorem 4.7에 의해 유일한 해가 존재한다.

$x$는 $a$의 법 $p$에 대한 모듈러 역원이다.

$p$가 소수이므로 $a^2 \equiv 1 \pmod p$ 일 때의 필요충분조건은 $a=1$ 혹은 $a=p-1$ 이다.

$1$과 $p-1$를 제외하면, $2,3,\dots,p-2$ 는 $a \ne x$ 이고 그들의 곱 $ax \equiv 1 \pmod p$ 인 쌍 $a$와 $x$를 짝지을 수 있다.

이러한 $(p-3)/2$ 개의 합동식을 서로 곱하고 약수를 재배열하자.

$$ \begin{gathered} 2 \cdot 3 \cdots (p-2) \equiv 1 \pmod p\\ (p-2)! \equiv 1 \pmod p \end{gathered} $$

이제 양변에 $p-1$ 를 곱하면,

$$ \begin{gathered} (p-1)! \equiv p-1 \pmod p\\ \downarrow\\ (p-1)! \equiv -1 \pmod p \end{gathered} $$

$\square$

---

예시를 보자.

$p=13$ 일 때, $1 \cdot 1 \equiv 1 \pmod {13}$과 $12 \cdot 12 \equiv 1 \pmod {13}$ 를 논외로 하고,

$$ \begin{gathered} 2 \cdot 7 \equiv 1 \pmod {13}\\ 3 \cdot 9 \equiv 1 \pmod {13}\\ 4 \cdot 10 \equiv 1 \pmod {13}\\ 5 \cdot 8 \equiv 1 \pmod {13}\\ 6 \cdot 11 \equiv 1 \pmod {13} \end{gathered} $$

의 양변을 모두 곱하자.

$$ \begin{aligned} 11! &\equiv 1 \pmod {13} \\ 12! &\equiv 12 \equiv -1 \pmod {13}\\ \therefore 12! &\equiv -1 \pmod {13} \end{aligned} $$

윌슨의 정리의 역

윌슨의 정리는 역도 참이다.

즉, $(p-1)! \equiv 1 \pmod p$ 이면, $p$는 소수이다.

증명

$(n-1)! \equiv -1 \pmod n$ 이면, $n$은 소수이다.

$n$이 소수가 아니라고 가정하면,

$$ n=ds(1 < d \le s

이라 하자.

$d \mid n$이므로 $(n-1)! \equiv -1 \pmod d$ 도 성립해야 한다.

그런데 $d \mid (n-1)!$ 이므로 $(n-1)! \equiv 0 \equiv -1 \pmod d$ 가 된다.

$d \mid 1$ 이 되고 $d > 1$ 이라 모순이다.

그러므로 $n$은 소수이다. $\square$

이차합동식과 윌슨의 정리

Theorem 5.5

홀수인 소수 $p$에 대해 이차 합동식 $x^2+1 \equiv 0 \pmod p$ 가 해를 가질 조건은 $p \equiv 1 \pmod 4$ 이다.

이는 역도 성립한다.

증명

$a$를 $x^2+1 \equiv 0 \pmod p$의 임의의 해라고 하면, $a^2 \equiv -1 \pmod p$

$p \nmid a$ 이므로 페르마의 정리에 의해

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

따라서 $p=4k+3$ 형태는 불가능하다. 그렇지 않다면,

$(-1)^{(4k+2)/2} = (-1)^{2k+1} = -1$ 이기 때문에,

$1 \equiv -1 \pmod p$ 가 되어 모순이다.

따라서 $p$는 $4k+1$의 형태를 갖는다.

역 증명

$p \equiv 1 \pmod 4 \Longrightarrow x^2+1 \equiv 0 \pmod p$ 가 해를 가진다.

를 증명해보자.

다음과 같은 곱을 보자.

$$ \begin{aligned} (p-1)! &\equiv 1 \cdot 2 \cdots (p-1)/2 \cdot (p+1)/2 \cdots (p-1)\\ p-1 &\equiv -1 \pmod p\\ p-2 &\equiv -2 \pmod p\\ \vdots\\ (p+1)/2 &\equiv -(p-1)/2 \pmod p \end{aligned} $$

인수를 재배열하여 $(p-1)/2$ 개의 음수가 포함되어 있어서

$$ \begin{aligned} (p-1)! &\equiv 1 \cdot (-1) \cdot 2 \cdot (-2) \cdots \left((p-1)/2\right)\left( -(p-1)/2 \right)\\ &\equiv (-1)^{(p-1)/2}\left[ \left( \dfrac {p-1}2 \right)! \right]^2 \pmod p \end{aligned} $$

윌슨의 정리를 이용해 $(p-1)! \equiv -1 \pmod p$ 이므로,

$$ \begin{aligned} -1 \equiv (-1)^{(p-1)/2}\left[ \left( \dfrac {p-1}2 \right)! \right]^2 \pmod p \end{aligned} $$

$p=4k+1$ 라고 가정하면,

$$ \begin{aligned} -1 \equiv \left[ \left( \dfrac {p-1}2\right)! \right]^2 \pmod p \end{aligned} $$

따라서 정수 $((p-1)/2)!$ 이 $x^2 + 1 \equiv 0 \pmod p$ 를 만족하게 된다. $\square$