6. 페르마의 (작은)정리, 윌슨의 정리

6. 페르마의 (작은)정리, 윌슨의 정리

페르마의 정리(Fermat's theorem)

\(p\)를 소수, \(p\not|a\)라 하자. 그러면 \(a^{p-1}\equiv1\,(\text{mod}\,p)\)이다.

증명: 집합 \(\{a,\,2a,\,\cdots,\,(p-1)a\}\)는 법 \(p\)로 합동이 아니다. 이 집합의 두 원소 \(ia,\,ja\,(1\leq i,\,j\leq p-1)\)에 대하여

\(ia\equiv ja\,(\text{mod}\,p)\)라고 하면, \(p|a(i-j)\)이고, \(p\not|a\)이므로 \(p|i-j\)이고, \(|i-j|<p-1\)이므로 \(i=j\)이어야 한다.

두 집합 \(\{1,\,2,\,\cdots,\,p-1\}\), \(\{a,\,ap,\,\cdots,\,a(p-1)\}\)의 원소는 적당한 짝을 이루어 합동이고$$a\cdot2a\cdots(p-1)a\equiv1\cdot2\cdots(p-1)\,(\text{mod}\,p)$$이므로 \((p-1)!a^{p-1}\equiv(p-1)\,(\text{mod}\,p)\)이고 \(\text{gcd}((p-1)!,\,p)=1\)이므로 따라서 \(a^{p-1}\equiv1\,(\text{mod}\,p)\)이다.

\(5^{38}\)을 \(11\)로 나눈 나머지를 구하자. \(11\)은 소수이고 \(11\not|5\)이므로 페르마의 정리에 의해 \(5^{10}\equiv1\,(\text{mod}\,11)\)이다. 그러면 \(5^{38}=(5^{10})^{3}\cdot5^{8}\)이므로 \(5^{38}\equiv5^{8}\,(\text{mod}\,11)\)이고,$$(5^{2})^{4}\equiv25^{4}\equiv3^{4}\equiv81\equiv4\,(\text{mod}\,11)$$이므로 따라서 \(5^{38}\)을 \(11\)로 나눈 나머지는 \(4\)이다.

페르마의 정리의 대우명제는 "\(a^{n}\not\equiv a\,(\text{mod}\,p)\)이면, \(n\)은 소수가 아니다"이고, 이를 이용하여 \(n\)이 소수인지 아닌지를 알 수있다. 

\(2^{7}=128\equiv11\,(\text{mod}\,117)\)이므로,$$\begin{align*}2^{117}=2^{7\cdot16+5}&\equiv(11)^{16}\cdot32\equiv4^{8}\cdot2^{5}\equiv2^{21}\\&\equiv(2^{7})^{3}\equiv11^{3}\\&\equiv44\end{align*}$$이고 \(2^{117}\equiv44\not\equiv2\,(\text{mod}\,117)\)이므로 따라서 \(117\)은 소수가 아니다.

페르마의 정리의 역은 성립하지 않는다.

\(p\)와 \(q\)를 서로다른 소수라 하고 \(a^{p}\equiv a\,(\text{mod}\,q)\), \(a^{q}\equiv a\,(\text{mod}\,p)\)라 하자. 그러면 \(a^{pq}\equiv a\,(\text{mod}\,pq)\)이다.

증명: \(a^{pq}=(a^{p})^{q}\equiv a^{q}\,(\text{mod}\,q)\)이고, \(a^{pq}\equiv(a^{q})^{p}\equiv a^{p}\,(\text{mod}\,p)\)이므로 \(p|a^{pq}-a\), \(q|a^{pq}-a\)이고 \(pq|a^{pq}-a\)이므로 따라서 \(a^{pq}\equiv a\,(\text{mod}\,pq)\)이다.

\(341=11\cdot31\)이고, \(11,\,31\)은 소수이다. \(2^{10}=1024=31\cdot33+1\)이므로$$2^{11}\equiv2\cdot2^{10}\equiv2\cdot1=2\,(\text{mod}\,31)$$이고$$2^{31}=2(2^{10})^{3}\equiv2\cdot1^{3}\equiv2\,(\text{mod}\,11)$$이므로 앞의 정리에 의해 \(2^{11\cdot31}\equiv2\,(\text{mod}11\cdot31)\)이고, 따라서 \(2^{340}\equiv1\,(\text{mod}\,341)\)이다. 이는 페르마의 정리의 역이 성립하지 않음을 보여주는 반례이다.

윌슨의 정리(Wilson's theorem)

\(p\)를 소수라고 하면, \((p-1)!\equiv-1\,(\text{mod}\,p)\)이다.

증명: \(p=2\)이면, \((2-1)!=1\equiv-1\,(\text{mod}\,2)\)이고, \(p=3\)이면, \((3-1)!=2\equiv-1\,(\text{mod}\,3)\)이다.

\(p>3\)일 때, \(a\)를 \(1,\,2\,\cdots,\,p-1\)중 하나라고 하면, \(\text{gcd}(a,\,p)=1\)이므로 일차합동식 \(ax\equiv1\,(\text{mod}\,p)\)의 해 \(x\)가 존재한다.

\(x=a\)이면, \(a^{2}\equiv1\,(\text{mod}\,p)\)이므로 \(p|a^{2}-1=(a-1)(a+1)\)이고, \(p|a-1\)또는 \(p|a+1\)이다.

\(p|a-1\)이면, \(a=1\)이고, \(p|a+1\)이면, \(a=p-1\)이다.

\(1\)과 \(p-1\)을 제외하면,$$a,\,a'\in\{2,\,3,\,\cdots,\,p-2\},\,a\neq a',\,aa'\equiv1\,(\text{mod}\,p)$$인 \(a,\,a'\)에 대해 얻어지는 합동식들을 모두 곱하면$$2\cdot3\cdots(p-2)=(p-2)!\equiv1\,(\text{mod}\,p)$$이고, 이 합동식에 \(p-1\)을 곱해주면$$(p-1)!\equiv p-1\equiv-1\,(\text{mod}\,p)$$이므로 윌슨의 정리를 얻는다.

\(p=13\)은 소수이고$$\begin{align*}2\cdot7&\equiv1\,(\text{mod}\,13)\\3\cdot9&\equiv1\,(\text{mod}\,13)\\4\cdot10&\equiv1\,(\text{mod}\,13)\\5\cdot8&\equiv1\,(\text{mod}\,13)\\6\cdot11&\equiv1\,(\text{mod}13)\end{align*}$$이므로 이 합동식들을 곱하면 \(11!\equiv1\,(\text{mod}\,13)\)이고, 이 합동식에 12를 곱하면 \(12!\equiv-1\,(\text{mod}\,13)\)이 된다.

윌슨의 정리의 역은 성립한다. 즉 \((n-1)!\equiv-1\,(\text{mod}\,n)\)이면, \(n\)은 소수이다.

증명: \((n-1)!\equiv-1\,(\text{mod}\,n)\)이고 \(n\)이 소수가 아니라고 하자. 그러면 \(d\,(1<d<n)\)가 존재해서 \(d|n\)이다. 

\(n|(n-1)!+1\)이므로 \(d|(n-1)!+n\)이고, 또한 \(d|(n-1)!\)이므로 \(d|1\)이 되는데 이는 모순이다.

\(15!\)을 17로 나눈 나머지를 구하자. \(17\)이 소수이므로 윌슨의 정리에 의해 \(16!\equiv-1\,(\text{mod}\,17)\)이다. \(15!\equiv a\,(\text{mod}\,17)\)이라고 하자. 이 합동식에 16을 곱하면 \(16!\equiv16a\equiv-1\equiv16\,(\text{mod}\,17)\)이고 따라서 \(a\equiv1\,(\text{mod}\,17)\)이므로 \(15!\)을 \(17\)로 나눈 나머지는 \(1\)이다.

윌슨의 정리를 응용해서 2차합동식 \(ax^{2}+bx+c\equiv0\,(\text{mod}\,n)\)의 해의 존재성을 보일 수 있다.

\(p\)가 홀수인 소수라고 하자. 이차합동식 \(x^{2}+1\equiv0\,(\text{mod}\,p)\)의 해가 존재할 필요충분조건은 \(p\equiv1\,(\text{mod}\,4)\)이다.

증명: 

\((\Rightarrow)\): 이차합동식\(x^{2}+1\equiv0\,(\text{mod}\,p)\)의 해 \(x\)가 존재한다고 하자. 그러면, \(x^{2}\equiv-1\,(\text{mod}\,p)\)이고, \(p\not| x\)이므로 페르마의 정리로부터 \(x^{p-1}\left(=(x^{2})^{\frac{p-1}{2}}\right)\equiv1\,(\text{mod}\,p)\)이다. \(p=4k+1\)임을 보이자. \(p=4k+3\)이라고 하면$$x^{p-1}\equiv(x^{2})^{\frac{p-1}{2}}\equiv(-1)^{\frac{p-1}{2}}=(-1)^{2k+1}=-1\,(\text{mod}\,p)$$이므로 \(1\equiv-1\,(\text{mod}\,p)\)이고 \(p|1-(-1)=2\)가 되는데 이는 모순이다.

\((\Leftarrow)\):$$(p-1)!=1\cdot2\cdot3\cdots\frac{p-1}{2}\frac{p+1}{2}\cdots(p-2)(p-1)$$이므로 다음의 합동식을 얻고$$\begin{align*}p-1&\equiv-1\,(\text{mod}\,p)\\p-2&\equiv-2\,(\text{mod}\,p)\\&\vdots\\\frac{p+1}{2}&\equiv-\frac{p-1}{2}\,(\text{mod}\,p)\end{align*}$$윌슨의 정리에 의해$$\begin{align*}-1\equiv(p-1)!&\equiv1\cdot(-1)\cdot2\cdot(-2)\cdots\frac{p-1}{2}\cdot\left(-\frac{p-1}{2}\right)\\&\equiv(-1)^{\frac{p-1}{2}}\left(1\cdot2\cdots\frac{p-1}{2}\right)^{2}=\left\{\left(\frac{p-1}{2}\right)!\right\}^{2}\,(\text{mod}\,p)\end{align*}$$이므로 따라서 \(\displaystyle\left(\left(\frac{p-1}{2}\right)!\right)^{2}+1\equiv0\,(\text{mod}\,p)\)이다.

\(p=13=4\cdot3+1\)이므로 \(\displaystyle x=\left(\frac{p-1}{2}\right)!=6!=720\equiv5\,(\text{mod}\,13)\)이고 따라서 \(x^{2}+1\equiv0\,(\text{mod}\,13)\)이다.

참고자료:

Elementary Number Theory 7th edition, Burton, McGraw-Hill