11. 르장드르 기호(1)

11. 르장드르 기호(1)

\(p\)를 홀수 소수, \(\text{gcd}(a,\,p)=1\)이라 하자. 르장드르 기호(Legendre symbol) \((a/p)\)를 다음과 같이 정의한다.$$(a/p)=\begin{cases}1,&\,(a는\,p의\,2차\,잉여류)\\-1,&\,(a는\,p의\,2차\,비잉여류)\end{cases}$$예를 들어 \(p=13\)일 때, \(p\)의 2차 잉여류가 \(1,\,3,\,4,\,9,\,10,\,12\)이므로$$\begin{align*}(1/13)&=(3/13)=(4/13)=(9/13)=(10/13)=(12/13)=1\\(2/13)&=(5/13)=(6/13)=(7/13)=(8/13)=(11/13)=-1\end{align*}$$

\(p\)를 홀수 소수, \(\text{gcd}(a,\,p)=1,\,\text{gcd}(b,\,p)=1\)이라 하자. 그러면 다음 성질들이 성립한다.

(a) \(a\equiv b\,(\text{mod}\,p)\)이면, \((a/p)=(b/p)\)이다.

(b) \((a^{2}/p)=1\)

(c) \((a/p)\equiv a^{\frac{p-1}{2}}\,(\text{mod}\,p)\)

(d) \((ab/p)=(a/p)(b/p)\)

(e) \((1/p)=1\)이고 \((-1/p)=(-1)^{\frac{p-1}{2}}\)

증명: (a), (b), (c)는 자명하다.

(d): \((ab/p)\equiv(ab)^{\frac{p-1}{2}}\,(\text{mod}\,p)\)라 하면, (c)에 의해$$(ab)^{\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv(a/p)(b/p)\,(\text{mod}\,p)$$이다. 만약 \((ab/p)\neq(a/p)(b/p)\)이면, \(1\equiv-1\,(\text{mod}\,p)\)이고 \(p|2\)가 되는데, \(p\)는 홀수 소수이므로 모순이다. 그러므로 \((ab/p)=(a/p)(b/p)\)이어야 한다.

(e): \((1/p)=1\)은 분명하고, (c)에 의해 \((-1/p)=(-1)^{\frac{p-1}{2}}\)이다.

\((a^{2}/p)=1\)이므로 \((a^{2}b/p)=(a^{2}/p)(b/p)=(b/p)\)이다.

2차 합동식 \(x^{2}\equiv-46\,(\text{mod}\,17)\)의 해가 존재하는지 확인하자. \(p=17\)이므로$$(-46/17)=(-1/17)(46/17)=(46/17)$$이고 \(46\equiv12\,(\text{mod}\,17)\)이므로$$(46/17)=(12/17)=(2^{2}/17)(3/17)=(3/17)$$이다. 이때$$(3/17)=3^{\frac{17-1}{2}}\equiv3^{8}\equiv(81)^{2}\equiv(-4)^{2}\equiv-1\,(\text{mod}\,17)$$이므로 \((3/17)=-1\)이고 \((-46/17)=-1\)이므로 이 2차 합동식의 해는 존재하지 않는다.

\(p=4k+1\)형태의 소수는 무한히 많다.

증명: \(4k+1\)형태의 소수가 유한개(\(p_{1},\,\cdots,\,p_{n}\)) 있다고 하고 \(N=(2p_{1}\cdots p_{n})^{2}+1\)이라 하자.

\(N\)은 홀수이므로 산술의 기본정리로부터 적당한 소수 \(p\)가 존재해서 \(p|N\)이다. 이것은$$(2p_{1}\cdots p_{n})^{2}\equiv-1\,(\text{mod}\,p)$$를 뜻하고, 따라서 \(p\)는 \(4k+1\)형태의 소수이어야 한다. 이것은 \(p\)가 \(p_{1},\,\cdots,\,p_{n}\)중 하나여야 함을 뜻하고  \(p|(2p_{1}\cdots p_{n})^{2}\)이므로 \(p|N-(2p_{1}\cdots p_{n})^{2}=1\)이 되는데 이는 모순이다. 따라서 \(4k+1\)형태의 소수는 무한히 많다.

\(p\)를 홀수 소수라고 하자. 그러면 \(\displaystyle\sum_{a=1}^{p-1}{(a/p)}=0\)이다. 이것은 2차 잉여류와 비잉여류가 각각 \(\displaystyle\frac{p-1}{2}\)개 있음을 뜻한다.

증명: \(r\)을 \(p\)의 원시근이라고 하자. 그러면 법 \(p\)에서 \(1,\,2,\,\cdots,\,p-1\)은 \(r,\,r^{2},\,\cdots,\,r^{p-1}\)과 합동이고$$\sum_{a=1}^{p-1}{(a/p)}=\sum_{k=1}^{p-1}{(r^{k}/p)}=\sum_{k=1}^{p-1}{(r/p)^{k}}$$가 성립하는데 \((r/p)=-1\)이어야 한다.

만약 \((r/p)=1\)이면, \(x\in\mathbb{Z}\)가 존재해서 \(x^{2}\equiv r\,(\text{mod}\,p)\)이고 페르마 정리에 의해$$(x^{2})^{\frac{p-1}{2}}\equiv r^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)$$가 되는데 이는 \(r\)이 \(p\)의 원시근이라는 사실에 모순이다.

그러므로 \(\displaystyle\sum_{a=1}^{p-1}{(a/p)}=\sum_{k=1}^{p-1}{(-1)^{k}}=0\)(\(\because\) \(p-1\)은 짝수)이다.

\(p\)를 홀수 소수, \(r\)을 \(p\)의 원시근이라고 하자. 그러면 다음 식이 성립한다.$$r^{k}=\begin{cases}\text{2차 잉여류}&,\,(k:\,\text{even})\\ \text{2차 비잉여류}&,\,(k:\,\text{odd})\end{cases}$$

\(Q\)를 2차 잉여류, \(N\)을 2차 비잉여류라고 하자. 그러면 다음이 성립한다.$$QQ=N,\,QN=N,\,NN=Q$$

\(2\)는 \(p=13\)의 원시근이므로$$\begin{align*}2^{2}&=4\equiv4\,(\text{mod}\,13)\\2^{4}&=16\equiv3\,(\text{mod}\,13)\\2^{6}&=64\equiv12\,(\text{mod}\,13)\\2^{8}&=256\equiv9\,(\text{mod}\,13)\\2^{10}&=1024\equiv10\,(\text{mod}\,13)\\2^{12}&=4096\equiv1\,(\text{mod}\,13)\end{align*}$$는 2차 잉여류이고,$$\begin{align*}2^{1}&=2\equiv2\,(\text{mod}\,13)\\2^{3}&=8\equiv8\,(\text{mod}\,13)\\2^{5}&=32\equiv6\,(\text{mod}\,13)\\2^{7}&=128\equiv11\,(\text{mod}\,13)\\2^{9}&=512\equiv5\,(\text{mod}\,13)\\2^{11}&=2048\equiv7\,(\text{mod}\,13)\end{align*}$$은 2차 비잉여류이다.

가우스 보조정리(Gauss's lemma)

\(p\)를 홀수 소수, \(\text{gcd}(a,\,p)=1\), \(\displaystyle S=\left\{a,\,2a,\,3a,\,\cdots,\,\left(\frac{p-1}{2}\right)a\right\}\), \(n\)을 집합 \(S\)의 원소 중 \(p\)로 나누어서 나머지가 \(\displaystyle\frac{p}{2}\)보다 큰 원소의 개수라고 하자. 그러면$$(a/p)=(-1)^{n}$$이다.

증명: \(r_{1},\,r_{2},\,\cdots,\,r_{m}\)을 \(S\)의 원소 중에서 \(p\)로 나누었을 때, 나머지가 \(0\)보다 크고 \(\displaystyle\frac{p}{2}\)보다 작은 나머지들이라고 하고,

\(S_{1},\,S_{2},\,\cdots,\,S_{n}\)을 \(S\)의 원소 중에서 \(p\)로 나누었을 때, 나머지가 \(\displaystyle\frac{p}{2}\)보다 크고 \(p\)보다 작은 나머지들이라고 하자.

그러면 \(\displaystyle m+n=\frac{p-1}{2}\)이고 \(r_{1},\,\cdots,\,r_{m},\,p-S_{1},\,\cdots,\,p-S_{n}\)은 모두 \(\displaystyle\frac{p}{2}\)보다 작고 서로 다른 정수들이다.

\(S\)의 원소들은 법 \(p\)로 서로 합동이 아니므로 \(r_{i_{1}}\neq r_{i_{2}}\)이고 \(p-S_{j_{1}}\neq p-S_{j_{2}}\)이다. 만약 서로 합동이라면 어떤 \(i\)와 \(j\)에 대해 \(r_{i}=p-S_{j}\)이므로 \(\displaystyle1\leq u,\,v\leq\frac{p-1}{2}\)인 \(u,\,v\)가 존재해서$$ua\equiv r_{i}\,(\text{mod}\,p),\,va\equiv S_{j}\,(\text{mod}\,p)$$이다. 그러면$$(u+v)a\equiv r_{i}+S_{j}\equiv p\equiv0\,(\text{mod}\,p)$$이고 \((u+v)\equiv0\,(\text{mod}\,p)\)가 되는데 \(1<u+v\leq p-1\)이므로 모순이다.

집합 \(\displaystyle\left\{r_{1},\,\cdots,\,r_{m},\,p-S_{1},\,\cdots,\,p-S_{n}\right\}\)은 \(\displaystyle\frac{p-1}{2}\)개의 원소를 가지고 있고, 모두 \(\displaystyle\frac{p}{2}\)보다 작고 집합 \(\displaystyle\left\{1,\,2,\,\cdots,\,\frac{p-1}{2}\right\}\)과 같다. 그러면$$\begin{align*}\left(\frac{p-1}{2}\right)!&=r_{1}\cdots r_{m}(p-S_{1})\cdots(p-S_{n})\\&\equiv r_{1}\cdots r_{m}(-S_{1})\cdots(-S_{n})\,(\text{mod}\,p)\\&\equiv(-1)^{n}r_{1}\cdots r_{m}S_{1}\cdots S_{n}\,(\text{mod}\,p)\end{align*}$$이고 \(r_{1},\,\cdots,\,r_{m},\,S_{1},\,\cdots,\,S_{n}\)은 법 \(p\)에 대해 어떤 순서로 \(\displaystyle a,\,2a,\,\cdots,\,\left(\frac{p-1}{2}\right)a\)이므로$$\begin{align*}\left(\frac{p-1}{2}\right)!&\equiv(-1)^{n}a\cdot2a\cdots\left(\frac{p-1}{2}\right)a\,(\text{mod}\,p)\\&\equiv(-1)^{n}a^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!\,(\text{mod}\,p)\end{align*}$$이고 \(\displaystyle\left(\frac{p-1}{2}\right)!\)과 \(p\)는 서로소이므로$$1\equiv(-1)^{n}a^{\frac{p-1}{2}}\,(\text{mod}\,p)$$이고$$(-1)^{n}\equiv a^{\frac{p-1}{2}}\equiv(a/p)\,(\text{mod}\,p)$$이므로 따라서$$(a/p)=(-1)^{n}$$이다.

\(p=13,\,a=5\)일 때, \(\displaystyle\frac{p-1}{2}=6\)이고 \(S=\{5,\,10,\,15,\,20,\,25,\,30\}\)이므로 집합 \(S\)의 원소들 각각을 \(13\)으로 나눈 나머지가 \(5,\,10,\,2,\,7,\,12,\,4\)이므로 이것들을 집합으로 나타내면 \(\{2,\,4,\,5,\,7,\,10,\,12\}\)이고 \(\displaystyle\frac{13}{2}\)보다 큰 원소는 \(7,\,10,\,12\)이므로 \((5/13)=(-1)^{3}=-1\)이다.

\(p\)를 홀수 소수라고 하자. 그러면 다음이 성립한다.$$(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}$$

증명: 가우스 보조정리에 의해 \((2/p)=(-1)^{n}\)이고 \(n\)을 집합 \(\displaystyle S=\left\{1\cdot2,\,2\cdot2,\,\cdots,\,\left(\frac{p-1}{2}\right)2\right\}\)의 원소들을 \(p\)로 나누었을 때, 나머지가 \(\displaystyle\frac{p}{2}\)보다 큰 원소들의 개수라고 하면 \(S\)의 원소들은 \(2\)와 \(p-1\)사이에 있으므로 \(S\)의 원소 중에서 \(\displaystyle\frac{p}{2}\)보다 큰 원소의 개수를 세면 된다.  즉 \(\displaystyle1\leq k\leq\frac{p-1}{2}\)일 때 \(\displaystyle 2k<\frac{p}{2}\)일 필요충분조건은 \(\displaystyle k<\frac{p}{4}\)이므로 \([]\)를 가우스 함수(\([x]\)는 \(x\)를 넘지 않는 최대의 정수)라고 하면 \(\displaystyle p=\frac{p-1}{2}-\left[\frac{p}{4}\right]\)이고 홀수 소수 \(p\)는 \(8k+1,\,8k+3,\,8k+5,\,8k+7\)중 하나이다.

\(p=8k+1\)일 때, \(\displaystyle n=4k-\left[\frac{8k+1}{4}\right]=2k\)이므로 \((2/p)=(-1)^{n}=(-1)^{2k}=1\)

\(p=8k+3\)일 때, \(\displaystyle n=\frac{8k+2}{2}-\left[\frac{8k+3}{4}\right]=2k+1\)이므로 \((2/p)=(-1)^{n}=(-1)^{2k+1}=-1\)

\(p=8k+5\)일 때, \(\displaystyle n=\frac{8k+4}{2}-\left[\frac{8k+5}{4}\right]=(4k+2)-(2k+1)=2k+1\)이므로 \((2/p)=(-1)^{n}=(-1)^{2k+1}=-1\)

\(p=8k+7\)일 때, \(\displaystyle n=\frac{8k+6}{2}-\left[\frac{8k+7}{4}\right]=(4k+3)-(2k+1)=2k+2\)이므로 \((2/p)=(-1)^{n}=(-1)^{2k+2}=1\)

이므로 이 정리가 성립한다. 

이 정리로부터 \(p\)가 홀수인 소수이면 \((2/p)=(-1)^{\frac{p^{2}-1}{8}}\)이 성립함을 알 수 있다. 

 

참고자료:

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