윌슨의 정리 확장판

윌슨의 정리를 한 번 볼까?

소수 $p$에 대해

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

정수론을 배우다보면 페르마의 소정리가 아래와 같이 일반화 된다.

$a^{p-1} \equiv 1 \pmod{p}, (p,a)=1$

$a^{\varphi(n)} \equiv 1 \pmod{n}, (n,a)=1$

윌슨의 정리는 $n$과 서로소인 수들의 곱을 $n$으로 나누었다고 볼 수 있다.

이를 일반화시켜보자.

 

<관찰>

5와 서로소인 자연수의 곱=$1\cdot 2\cdot 3\cdot 4= 24\equiv -1 \pmod{5}$

6과 서로소인 자연수의 곱=$1\cdot 5= 5 \equiv -1 \pmod{6}$

8과 서로소인 자연수의 곱=$1\cdot 3\cdot 5\cdot7 =105 \equiv 1 \pmod{8}$

관찰 결과 1 또는 -1이 나오는 것 같았다.

그래서 -1이 나오는 수들(N)의 규칙을 찾아내었다.

홀수인 소수 $p$와 자연수 $n$에 대해

$N= \begin{cases} 2 \\ 4 \\ p^{n} \\ 2p^{n} \end{cases}$

$N$은 집합 $\{\varphi(N)\}$과 그 원소 $i$에 대해 다음을 만족한다.

\[\prod_{i \in \varphi(N)} i \equiv -1 \pmod{N}\]

 

<증명>

<1> $p$

\[(p-1)! \equiv -1 \pmod{p}\]

임은 저번 포스팅에서 증명했었다.

 

<2> $2p$

$2p$와 서로소인 수는 홀수이면서 $p$의 배수가 아닌 수이다.

\[L=\color{Red}{1 \cdot  \cdot  \cdot (p-2)} \cdot \color{Blue}{(p+2) \cdot  \cdot  \cdot (2p-1)} \pmod{p}\]

\[\equiv 1 \cdot 2 \cdot 3 \cdot  \cdot  \cdot (p-1) \pmod{p}\]

\[\equiv (p-1)! \equiv -1 \pmod{p}\]

몫 $n$에 대해 다음이 성립한다.

\[L+1=np\]

좌변은 짝수이므로 $n=2m$

\[L=2mp-1\]

\[\therefore L \equiv -1 \pmod{2p}\]

 

<3> $p^{\alpha}$

\[L=\frac{(p^{\alpha}-1)!}{p^{p^{\alpha-1}-1}(p^{\alpha-1}-1)!} \equiv k \pmod{p^{\alpha}}\]

\[L=1 \cdot 2 \cdot  \cdot \cdot  (p-1) \cdot (p+1)  \cdot  \cdot  \cdot(2p-1) \cdot  \cdot  \cdot (p(p^{\alpha-1}-1)+1) \cdot  \cdot  \cdot (p^{\alpha}-1) \pmod{p}\]

\[\therefore L \equiv ((p-1)!)^{p^{\alpha-1}} \equiv -1 \pmod{p}\]

몫 $n$에 대해

\[L=np-1\]

\[L^{\alpha}=(np)^{\alpha}-_{\alpha}\mathrm{C}_{1}(np)^{\alpha-1}+\cdot\cdot\cdot+(-1)^{\alpha}\]

\[k^{\alpha} \equiv -_{\alpha}\mathrm{C}_{1}(k+1)^{\alpha-1}+\cdot\cdot\cdot+(-1)^{\alpha} \pmod{p^{\alpha}}\]

\[(k+1)^{\alpha}+k^{\alpha} \equiv ((k+1)+(-1))^{\alpha} \pmod{p^{\alpha}}\]

\[(k+1)^{\alpha} \equiv 0 \pmod{p^{\alpha}}\]

\[k \equiv -1 \pmod{p^{\alpha}}\]

\[\therefore \frac{(p^{\alpha}-1)!}{p^{p^{\alpha-1}-1}(p^{\alpha-1}-1)!} \equiv -1 \pmod{p^{\alpha}}\]

 

<4> $2p^{\alpha}$

\[L=1 \cdot 3 \cdot  \cdot  \cdot (p-2) \cdot (p+2) \cdot  \cdot  \cdot(2p^{\alpha}-1) \pmod{p^{\alpha}}\]

\[\equiv 1 \cdot 2 \cdot  \cdot  \cdot (p-1)\cdot  (p+1)\cdot  \cdot \cdot (p^{\alpha}-1) \pmod{p^{\alpha}}\]

\[\equiv \frac{(p^{\alpha}-1)!}{p^{p^{\alpha-1}-1}(p^{\alpha-1}-1)!} \equiv -1 \pmod{p^{\alpha}}\]

몫 $n$에 대해

\[L+1=np^{\alpha}\]

좌변은 짝수이므로 $n=2m$

\[L+1=2mp^{\alpha}\]

\[\therefore L \equiv -1 \pmod{2p^\alpha}\]

$\blacksquare$

 

# 2021-08-24 추가됨

위에 제시된 4종류의 수는 모두 원시근이 존재하는 수들이다. 원시근의 성질을 이용해서 -1과 합동임을 증명할 수 있다. 또 베주 항등식을 이용한 증명도 가능하다. 증명 과정은 윌슨의 정리를 증명하는 과정과 완전히 같기 때문에 다음 링크를 타고 가서 보는것이 좋을 것 같다.

 

윌슨의 정리 보러가기

 

베주 항등식을 이용한 증명의 엄밀성을 더하기 위해 다음 명제들을 증명하겠다. 

 

1. 2이상의 자연수 $k$에 대해 $2^{k}$과 서로소이고 $2^{k}$이하인 자연수$x$에 대해 $x^{2} \equiv 1 \pmod{2^{k}}$를 만족하는 $x$는 4개 뿐이다.

수 $x=2n+1$이라 두자($0 \le n \le 2^{k-1}-1$).이때 $x^{2} \equiv 1 \pmod{2^{k}}$라 두면

\[4n(n+1) \equiv \pmod{2^{k}}\]

$n=2^{k-2}+\alpha$($0 \le \alpha \le 2^{k-2}-1$) 라 두자. 

\[4n(n+1) \equiv 4\alpha(\alpha+1) \pmod{2^{k}}\]

이때 $\alpha=0, 2^{k-2}-1$외에는 해가 없다. $n$으로 다시 쓰면 $n=2^{k-2}, 2^{k-1}-1$이고 $x$로 나타내면 $x=2^{k-1}+1, 2^{k}-1$이다. $x$의 해는 $2^{k-1}$에 대해 대칭적으로 분포하므로 오직 4개 뿐임을 확인할 수 있다.

 

2. 소수 $p$와 2 이상의 자연수 $k$에 대해 $p^{k}$과 서로소이고 $p^{k}$이하인 자연수 $x$가 $x^{2} \equiv 1 \pmod{p^{k}}$를 만족할 때 법 $p^{k}$에 대한 $x$의 역원은 자기 자신 뿐이다. 

$x$에 $p^{k}$를 더하거나 빼는 순간 제시된 범위를 벗어난다. 

 

3. 홀수인 소수 $p$와 2 이상의 자연수 $k$에 대해  $p^{k}$과 서로소이고 $p^{k}$이하인 자연수 $x$ 중 $x^{2} \equiv 1 \pmod{p^{k}}$를 만족하는 수는 2개 뿐이다.

$x=pn+q$이라 두자. 단, $\gcd(p,q)=1,\ 0<q<p,\ 0 \le n \le \left[\frac{p^{k}-q}{p}\right] = p^{k-1}-1$.

\[(pn+q)^{2} \equiv 1 \pmod{p^{k}}\]

\[(pn+q+1)(pn+q-1) \equiv 0 \pmod{p^{k}}\]

$(pn+q+1)$이 $p$로 나누어 떨어진다면 $(pn+q-1)$이 $p$로 나누어 떨어지지 않는다. 그 반대의 경우도 마찬가지다. $(pn+q+1)$이 $p$로 나누어 떨어진다 가정하자. 이때 $q+1=p$가 된다. 그럼 $(pn+q+1)=p(n+1)$이 되며 $n+1$이 $p^{k-1}$으로 나누어 떨어지면 된다. $n=p^{k-1}$이면 성립한다. 따라서 $x=p^{k}-1$이다. 이 반대의 경우를 해보면 $n=0$이 나오고 $x=1$이 된다. $x=1, p^{k}-1$ 2가지의 경우다. 

 

$x^{2} \equiv 1 \pmod{p^{k}}$를 만족하는 $x$는 또다른 $x$와 곱해서 -1이라는 결과를 낳는다. 따라서 $k$를 $x$의 개수라 정의한다면 $p^{k}$이하의 $p^{k}$과 서로소인 수들의 곱은 $(-1)^{k/2}$가 되는 것이다. 따라서 $2^{k}$은 $N$이 될 수 없다.