12. 르장드르 기호(2: 2차상호법칙)

12. 르장드르 기호(2: 2차상호법칙)

\(p\)와 \(2p+1\)이 모두 홀수인 소수라고 하자. 그러면 \((-1)^{\frac{p-1}{2}}2\)는 \(2p+1\)의 원시근이다.

증명: \(q=2p+1\)이라 하자.

(1) \(p=4k+1\)이면, \((-1)^{\frac{p-1}{2}}=(-1)^{\frac{4k}{2}}=1\)이므로 \(2\)는 \(q\)의 원시근이 되는데 \(2\)의 위수가 \(\phi(q)=q-1=2p\)이기 때문이다. 그러면 \(2\)의 위수는 \(1,\,2,\,p,\,2p\)중 하나이다.

분명히 \(2^{1}\not\equiv1\,(\text{mod}\,q)\)이므로 \(1\)은 \(2\)의 위수가 아니다.

\(2\)는 \(2\)의 위수가 아니다. 만약 \(2^{2}\equiv1\,(\text{mod}\,q)\)이면, \(q|3\)이므로 \(q=3,\,p=1\)이 되는데 이는 모순이다.

\(p\)는 \(2\)의 위수가 아니다. 만약 \(2^{p}\equiv1\,(\text{mod}\,q)\)이면, \(2^{\frac{q-1}{2}}\equiv1\,(\text{mod}\,q)\)이므로 \((2/q)=1\)이고 \(q=8k\pm1\)이 되어 \(p=4k\) 또는 \(p=4k-1\)이 되는데 이는 모순이다.

\(\text{gcd}(2,\,p)=1\)이므로 오일러 정리에 의해 \(2^{\phi(q)}=2^{2p}\equiv1\,(\text{mod}\,q)\)이고 따라서 \(2\)는 \(q\)의 원시근이다.

(2) \(p=4k+3\)이면, \((-1)^{\frac{p-1}{2}}=(-1)^{2k+1}=-1\)이므로 \(-2\)는 \(q\)의 원시근이 되는데 \(2\) 의 위수가 \(\phi(q)=2p\)이고 \((-2)^{1},\,(-2)^{2},\,\cdots,\,(-2)^{p}\)모두 법 \(p\)로 합동이 아니기 때문이다.

\(1\)은 \(-2\)의 위수가 아니다. \(-2\equiv1\,(\text{mod}\,q\)이면 \(q|3\)이고 \(q=3\)이 되는데 \(p=1\)이 되어 모순이다.

\(2\)는 \(-2\)의 위수가 아니다. \((-2)^{2}\equiv1\,(\text{mod}\,q)\)이면 \(q|3\)이고 위와 같은 이유로 모순이다.

\(p\)는 \(-2\)의 위수가 아니다. \((-2)^{p}\equiv1\,(\text{mod}\,q)\)이면 \((-2)^{}\frac{q-1}{2}\equiv1\,(\text{mod}\,q)\)이고 \((-2/q)=(-1/q)(2/q)=1\)이므로 \(p=4k+3\)이고 \(q=8k+7=4(2k+1)+3\)이 되어 \((-1/q)=-1\), \((2/q)=1\)이고 \((-2/q)=(-1/q)(2/q)=-1\)이 되는데 \(1=-1\)이라는 모순이 도출된다.

따라서 \(-2\)의 위수는 \(2p\)이고 \(-2\)는 \(q\)의 원시근이다.

\(p\)를 홀수 소수라고 하고 \(a\)를 \(\text{gcd}(a,\,d)=1\)인 홀수라고 하면 다음 식이 성립한다.$$(a/p)=(-1)^{\sum_{k=1}^{\frac{p-1}{2}}{[\frac{ka}{p}]}}$$(\([x]\)는 \(x\)를 넘지 않는 최대의 정수이다)

증명: \(\displaystyle S=\left\{a,\,2a,\,\cdots,\,\left(\frac{p-1}{2}\right)a\right\}\)라 하고, \(S\)의 원소를 \(p\)로 나누었을 때, 나머지가 \(\displaystyle\frac{p}{2}\)보다 작은 원소의 나머지들을 \(\{r_{1},\,\cdots,\,r_{m}\}\), 나머지가 \(\displaystyle\frac{p}{2}\)보다 큰 원소의 나머지들을 \(\{S_{1},\,\cdots,\,S_{n}\}\), \(p\)로 나눈 결과를$$ka=q_{k}p+t_{k}\,\left(0\leq t_{k}<p,\,1\leq k\leq\frac{p-1}{2}\right)$$라고 하자. 그러면 \(\displaystyle\frac{ka}{p}=q_{k}+\frac{t_{k}}{p}\)이고 \(\displaystyle\left[\frac{ka}{p}\right]=q_{k}\)이므로 따라서 \(\displaystyle ka=\left[\frac{ka}{p}\right]p+t_{k}\)이다.$$\sum_{k=1}^{\frac{p-1}{2}}{ka}=\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{ka}{p}\right]p}+\sum_{k=1}^{\frac{p-1}{2}}{t_{k}}=\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{ka}{p}\right]p}+\sum_{k=1}^{m}{r_{k}}+\sum_{j=1}^{n}{S_{j}}\,(1)$$이고 \(\displaystyle\{r_{1},\,\cdots,\,r_{m},\,p-S_{1},\,\cdots,\,S_{n}\}=\{1,\,\cdots,\,\frac{p-1}{2}\}\)이므로$$\sum_{k=1}^{\frac{p-1}{2}}{k}=\sum_{k=1}^{m}{r_{k}}+pn-\sum_{j=1}^{n}{S_{j}}\,(2)$$이고 \((1)\)식을 \((2)\)식으로 빼면$$(a-1)\sum_{k=1}^{\frac{p-1}{2}}{k}=\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{ka}{p}\right]p}-pn+2\sum_{j=1}^{n}{S_{j}}$$이고 \(a\)가 홀수이므로 \(a-1\)은 짝수이다. 그러면$$0\equiv\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{ka}{p}\right]p}-pn\,(\text{mod}\,2)$$이고 \(\text{gcd}(2,\,p)=1\)이므로$$n\equiv\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{ka}{p}\right]}\,(\text{mod}\,2)$$이고 따라서 가우스 보조정리에 의해$$(a/p)=(-1)^{n}=(-1)^{\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{ka}{p}\right]}}$$이다.

\((5/13)\,(a=5,\,p=13)\)일 때, \(\displaystyle\frac{p-1}{2}=6\)이므로$$\left[\frac{5}{13}\right]=0,\,\left[\frac{10}{13}\right]=0,\,\left[\frac{15}{13}\right]=1,\,\left[\frac{20}{13}\right]=1,\,\left[\frac{25}{13}\right]=1,\,\left[\frac{30}{13}\right]=2$$이고 위의 결과에 의해$$(5/13)=(-1)^{1+1+1+2}=(-1)^{5}=-1$$이다.

2차상호법칙(Quadratic Reciprocity Law)

\(p\)와 \(q\)가 서로 다른 홀수이면$$(p/q)(q/p)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$이다.

증명: \(R\)을 꼭짓점이 \(\displaystyle(0,\,0),\,\left(\frac{p}{2},\,0\right),\,\left(0,\,\frac{q}{2}\right),\,\left(\frac{p}{2},\,\frac{q}{2}\right)\)인 직사각형의 경계선을 포함하지 않은 내부영역 이라 하고(아래 그림 참고)

\(D\)를 원점 \((0,\,0)\)과 점 \(\displaystyle\left(\frac{p}{2},\,\frac{q}{2}\right)\)를 잇는 대각선, \(T_{1}\)을 대각선 \(D\) 아래에 있는 \(R\)의 영역, \(T_{2}\)를 대각선 \(D\) 위에 있는 \(R\)의 영역이라고 하자.

대각선 \(D\)의 방정식은 \(\displaystyle y=\frac{q}{p}x\,(py=qx)\)이고, \(D\)위에는 \(xy\)좌표가 모두 정수인 점은 없다.

만약 있다고 하면 \(p|qx\)이고 \(p|x\)가 되어 \(x\geq p\)가 되는데 \(\displaystyle0<x<\frac{p}{2}\)이므로 모순이다.

\(\displaystyle 1\leq x\leq\frac{p}{2},\,1\leq y\leq\frac{q}{2}\)이므로 \(R\)내부에 \(xy\)좌표가 모두 정수인 점들의 갯수는 \(\displaystyle\frac{p-1}{2}\frac{q-1}{2}\)이고 이것은 \(T_{1}\)내부의 정수 격자점수와 \(T_{2}\)내부의 정수 격자점수의 합이다.

\(x=k\)일 때, \(T_{1},\,T_{2}\)내부에 있는 정수 격자점들의 집합은 \(\displaystyle\left\{(k,\,y)\,|\,1\leq y<\frac{q}{p}k\right\}\)이고 그 갯수는 \(\displaystyle\left[\frac{kq}{p}\right]\)이고 따라서

\(T_{1}\) 내부에 있는 정수 격자점의 갯수는 \(\displaystyle\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{kq}{p}\right]}\)이고

\(T_{2}\) 내부에 있는 정수 격자점의 갯수는 \(\displaystyle\sum_{j=1}^{\frac{q-1}{2}}{\left[\frac{jp}{q}\right]}\)이므로$$\frac{p-1}{2}\frac{q-1}{2}=\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{kq}{p}\right]}+\sum_{j=1}^{\frac{q-1}{2}}{\left[\frac{jp}{q}\right]}$$이고 따라서$$(q/p)(p/q)=(-1)^{\sum_{k=1}^{\frac{p-1}{2}}{\left[\frac{kq}{p}\right]}}(-1)^{\sum_{j=1}^{\frac{q-1}{2}}{\left[\frac{jp}{q}\right]}}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$이다.

\(p,\,q\)가 모두 홀수 소수이면 다음이 성립한다.$$(p/q)=\begin{cases}(q/p),&\,(p\equiv1\,(\text{mod}\,4)\,\text{or}\,q\equiv1\,(\text{mod}\,4))\\-(q/p),&\,(p\equiv q\equiv3\,(\text{mod}\,4))\end{cases}$$

\(a\)의 소인수 분해를 \(a=\pm2^{k_{0}}p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\)이라 하자(\(p_{i}\)는 서로 다른 소수). 르장드르 기호는 승법적이므로$$(a/p)=(\pm1/p)(2/p)^{k_{0}}(p_{1}/p)^{k_{1}}\cdots(p_{r}/p)^{k_{r}}$$이다.$$\begin{align*}(-1/p)&=\begin{cases}1,&\,(p\equiv1\,(\text{mod}\,4))\\-1,&\,(p\equiv3\,(\text{mod}\,4))\end{cases}\\(2/p)&=\begin{cases}1,&\,(p\equiv1\,,(\text{mod}\,8)\,\text{or}\,p\equiv7\,(\text{mod}\,8))\\-1,&\,(p\equiv3\,(\text{mod}\,8)\,\text{or}\,p\equiv5\,(\text{mod}\,8))\end{cases}\end{align*}$$을 이용하면 앞의 \((-1/p),\,(2/p)\)는 해결할 수 있고, 나머지는 다음의 과정을 따르면 된다.

\(p_{i}>p\)이면, \((p_{i}/p)=(t_{i}/p)\)(\(t_{i}\)는 \(p_{i}\)를 \(p\)로 나눈 나머지)이고

\(p_{i}<p\)이면, 2차상호법칙을 적용한 후, 위 과정을 반복한다.

예를들어$$\begin{align*}(29/53)&=(53/29)=(24/29)=(2^{3}\cdot3/29)\\&=(2/29)^{3}(3/29)=(-1)^{3}(29/3)=(-1)(2/3)\\&=(-1)(-1)=1\end{align*}$$이다.

\(p\)를 \(3\)이 아닌 홀수 소수라고 하면 다음이 성립한다.$$(3/p)=\begin{cases}1,&\,(p\equiv\pm1\,(\text{mod}\,12))\\-1,&\,(p\equiv\pm5\,(\text{mod}\,12))\end{cases}$$

증명:$$(3/p)=\begin{cases}(p/3),&\,(p\equiv1\,(\text{mod}\,4))\\-(p/3),&\,(p\equiv3\,(\text{mod}\,4))\end{cases},\,(p/3)=\begin{cases}1,&\,(p\equiv1\,(\text{mod}\,3))\\-1,&\,(p\equiv2\,(\text{mod}\,3))\end{cases}$$이므로$$(3/p)=\begin{cases}1,&\,(p\equiv1\,(\text{mod}\,4)\,\text{and}\,p\equiv1\,(\text{mod}\,3))\\1,&\,(p\equiv3\,(\text{mod}\,4)\,\text{and}\,p\equiv2\,(\text{mod}\,3))\\-1,&\,(p\equiv1\,(\text{mod}\,4)\,\text{and}\,p\equiv2\,(\text{mod}\,3))\\-1,&\,(p\equiv3\,(\text{mod}\,4)\,\text{and}\,p\equiv1\,(\text{mod}\,3))\end{cases}$$이고 따라서 위의 결과를 얻는다.

참고자료:

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