오늘 트위터에서 쌍둥이 소수 $p, p + 2$가 있을 때, $p! ~\mathrm{mod}~ p + 2$를 구해보자! 라는 타래를 보고 예에전 학부때 배운 정수론이 떠올라서 기록해보았다.

윌슨 정리

$(p - 1)! \equiv -1 ~\mathrm{mod}~ p \text{ if and only if } p \text{ is a prime.}$

이 정리를 이용해서 처음의 문제를 풀면 굉장히 간단하게 풀린다: 이를 이용하면 $(p+1)! \equiv -1 ~\mathrm{mod}~ p+2 $ 임을 알 수 있고, 이는 다시 $(p+1)! \cdot (p+1)^{-1} \equiv -1 \cdot -1 \equiv 1 ~\mathrm{mod}~ p+2$로 깔끔하게 정리된다.

윌슨 정리의 증명

1. $p \text{ is a prime } \Rightarrow (p - 1)! \equiv -1 ~\mathrm{mod}~ p$

($p=2$일 때에는 성립하니까 $3$ 이상의 $p$에 대해서만 생각해보자) $x \in \{1, 2, …, p-1\}$은 모두 $p$와 서로소 관계이므로 각 $x$에 대해 $x\cdot{x^*}\equiv 1~\mathrm{mod}~ p$인 $x^* \in \{1, 2, …, p-1\}$가 존재한다. 여기서, $xx^* \equiv 1 ~\mathrm{mod}~ p$가 되는 $x$ 중에는 $x \equiv x^* ~\mathrm{mod}~ p$인 경우도 존재하는데, 이러한 경우에 $x \equiv \pm 1 ~\mathrm{mod}~ p$ 임을 알 수 있다(즉 $x = 1$ 또는 $x = p-1$). 따라서 $(p-1)! \equiv (p-1) \cdot 1 \cdot (p-2) \cdot … \cdot 2 \equiv -1 \cdot 1 \cdot 1 \equiv -1 ~\mathrm{mod}~ p$ 임을 확인할 수 있다.

2. $(p - 1)! \equiv -1 ~\mathrm{mod}~ p \Rightarrow p \text{ is a prime. } $

($p \leq 4$일 때에는 성립하니까 5 이상인 $p$에 대해서만 생각해보자) $p$가 소수가 아니라고(즉 $q | p$인 소수 $q$ 가 존재한다고) 가정하자. 이 경우 $q < p$이므로 $q | (p - 1)!$라는 결과가 나오는데, 이는 결국 $q \cdot q’ = p$인 $q$가 존재함을 의미하므로 $(p - 1)! = 0 \mathrm{mod} p$가 되어 모순이다. 따라서 $p$가 소수임을 확인할 수 있다.