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