10. 2차 잉여류, 오일러 판정법

10. 2차 잉여류, 오일러 판정법

홀수 소수 \(p\)와 \(\text{gcd}(a,\,p)=1\)인 \(a\)에 대하여 \(\text{gcd}(4a,\,p)=1\)이므로, 다음의 2차 합동식$$ax^{2}+bx+c\equiv0\,(\text{mod}\,p)$$에 대해 다음이 성립한다.$$\begin{align*}ax^{2}+bx+c\equiv0\,(\text{mod}\,p)&\Leftrightarrow4a(ax^{2}+bx+c)\equiv0\,(\text{mod}\,p)\\&\Leftrightarrow(2ax+b)^{2}+4ac-b^{2}\equiv0\,(\text{mod}\,p)\\&\Leftrightarrow(2ax+b)^{2}\equiv b^{2}-4ac\,(\text{mod}\,p)\end{align*}$$그러므로 이 2차 합동식을 \(y^{2}\equiv d\,(\text{mod}\,p)\,(y=2ax+b,\,d=b^{2}-4ac)\)의 형태로 나타낼 수 있다.

2차 합동식 \(5x^{2}-6x+2\equiv0\,(\text{mod}\,13)\)을 \(y^{2}\equiv(-6)^{2}-4\cdot5\cdot2=-4\equiv9\,(\text{mod}\,13)\,(y=10x-6)\)의 형태로 나타낼 수 있고,$$y^{2}-9\equiv(y+3)(y-3)\equiv0\,(\text{mod}\,13)$$이므로$$y\equiv3\,(\text{mod}\,13),\,y\equiv10\,(\text{mod}\,13)$$이다. 그러면 \(y=10x-6\)이므로 얻은 합동식들을$$10x\equiv9\,(\text{mod}\,13),\,10x\equiv16\,(\text{mod}\,13)$$의 형태로 나타낼 수 있고, \(4\cdot10\equiv1\,(\text{mod}\,13)\)이므로$$\begin{align*}x&\equiv4\cdot16=64\equiv12\,(\text{mod}\,13)\\x&\equiv4\cdot9=36\equiv10\,(\text{mod}\,13)\end{align*}$$이고, 따라서 이 2차 합동식의 해는$$x\equiv10\,(\text{mod}\,13),\,x\equiv12\,(\text{mod}\,13)$$이다.

\(p\)를 홀수 소수라 하고, \(\text{gcd}(a,\,p)=1\)이라 하자. 2차 합동식 \(x^{2}\equiv a\,(\text{mod}\,p)\)가 해를 가지면, \(a\)는 \(p\)의 2차 잉여류(quadratic residue)라고 하고, 그렇지 않으면 2차 비잉여류(quadratic nonresidue)라고 한다.

\(a\equiv b\,(\text{mod}\,p)\)라고 하자. \(a\)가 \(p\)의 2차 잉여류일 필요충분조건은 \(b\)가 \(p\)의 2차 잉여류인 것이고, 2차 잉여류는 \(1,\,2,\,\cdots,\,p-1\)중에서 생각한다.

\(p=13\)일 때, \(1,\,2,\,\cdots,\,12\)중에서 \(p=13\)의 2차 잉여류를 찾자.$$\begin{align*}1^{2}&\equiv12^{2}\equiv1\,(\text{mod}\,13)\\2^{2}&\equiv11^{2}\equiv4\,(\text{mod}\,13)\\3^{2}&\equiv10^{2}\equiv9\,(\text{mod}\,13)\\4^{2}&\equiv9^{2}\equiv3\,(\text{mod}\,13)\\5^{2}&\equiv8^{2}\equiv12\,(\text{mod}\,13)\\6^{2}&\equiv7^{2}\equiv10\,(\text{mod}\,13)\end{align*}$$이므로 \(1,\,3,\,4,\,9,\,10,\,12\)는 \(13\)의 2차 잉여류(결과)이고, 나머지인 \(2,\,5,\,6,\,7,\,8,\,11\)은 2차 비잉여류이다.

오일러 판정법(Euler's criterion)

\(p\)를 홀수 소수, \(\text{gcd}(a,\,p)=1\)이라고 하자. \(a\)가 \(p\)의 2차 잉여류일 필요충분조건은 \(a^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)\)이다.

증명:

\((\Rightarrow)\): \(a\)를 \(p\)의 2차 잉여류라고 하자. 그러면 \(x\in\mathbb{Z}\)가 존재해서 \(x^{2}\equiv a\,(\text{mod}\,p)\)이고 \(\text{gcd}(x,\,p)=1\)이다. 따라서 페르마 정리에 의해$$a^{\frac{p-1}{2}}\equiv(x^{2})^{\frac{p-1}{2}}\equiv x^{p-1}\equiv1\,(\text{mod}\,p)$$이다.

\((\Leftarrow)\): \(a^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)\)라고 하자. \(r\)을 \(p\)의 원시근이라고 하면 \(r^{p-1}\equiv1\,(\text{mod}\,p)\,(\because\phi(p)=p-1)\), \(r^{i}\not\equiv1\,(\text{mod}\,p)\,(1\leq i\leq p-2)\)이므로 \(k\,(1\leq k\leq p-1)\)가 존재해서 \(r^{k}\equiv a\,(\text{mod}\,p)\)이고, \((r^{k})^{\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)\)이므로 \(\displaystyle p-1|\frac{k(p-1)}{2}\)이고 \(2|k\,(k=2j)\)가 되어 \((r^{j})^{2}\equiv a\,(\text{mod}\,p)\)이므로 따라서 \(a\)는 \(p\)의 2차 잉여류이다.

\(p\)를 홀수 소수, \(\text{gcd}(a,\,p)=1\)이라 하자. \(a\)가 \(p\)의 2차 비잉여류일 필요충분조건은 \(a^{\frac{p-1}{2}}\equiv-1\,(\text{mod}\,p)\)이다.

증명:

\((\Rightarrow)\):$$\left(a^{\frac{p-1}{2}}-1\right)\left(a^{\frac{p-1}{2}}\right)=a^{p-1}-1\equiv0\,(\text{mod}\,p)$$이므로 \(a^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)\) 또는 \(a^{\frac{p-1}{2}}\equiv-1\,(\text{mod}\,p)\)이고, \(a\)가 \(p\)의 2차 비잉여류이므로 \(a^{\frac{p-1}{2}}\not\equiv1\,(\text{mod}\,p)\)이고 따라서 \(a^{\frac{p-1}{2}}\equiv-1\,(\text{mod}\,p)\)이다.

\((\Leftarrow)\): 다음의 합동식이 동시에 성립한다고 하자.$$a^{\frac{p-1}{2}}\equiv-1\,(\text{mod}\,p),\,a^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)$$그러면 \(1\equiv-1\,(\text{mod}\,p)\)이고 \(p|2\)가 되는데 이는 \(p\)가 홀수 소수라는 사실에 모순이다. 그러므로 \(a^{\frac{p-1}{2}}\not\equiv1\,(\text{mod}\,p)\)가 성립해야 하고 따라서 \(a\)는 \(p\)의 2차 비잉여류이다.

참고자료:

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