정의
\(p\)가 3 이상의 소수이고 \(a\)가 \((a,p)=1\)인 정수일 때, 다음 기호
- [math]\displaystyle{ \left(\frac{a}{p}\right)=\begin{cases} 1,& (\exists x\in \mathbb{Z})[x^2 = a]\\ -1,& (\forall x\in\mathbb{Z})[x^2\ne a] \end{cases} }[/math]
를 르장드르 기호(Legendre symbol)라고 한다. 즉, \(a\)가 법 \(p\)에 대한 이차잉여이면 \(\left(\frac{a}{p}\right)=1\)이고 그렇지 않으면 \(\left(\frac{a}{p}\right)=-1\)이다. 책에 따라서는 정의를 조금 확장하여, [math]\displaystyle{ p\mid a }[/math]이면 \(\left(\frac{a}{p}\right)=0\)이라 하기도 한다. 여기서는 \((a,p)=1\)인 경우만 고려한다.
기본 성질
\(p,q\)가 서로 다른 3 이상의 소수이고 정수 \(a,b\)에 대해 \((a,p)=(b,p)=1\)일 때,
- \(\left(\frac{a^2}{p}\right)=1\)
- \(x=a\)는 합동식 \(x^2\equiv a^2\pmod p\)의 해이므로 자명하다.
- \(a\equiv b \pmod p\)이면 \(\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)\)이다.
- \(a\equiv b \pmod p\)라고 가정하면 두 합동식 \(x^2\equiv a\pmod p\)와 \(x^2\equiv b\pmod p\)는 동치이므로 원하는 결론을 얻는다.
- \(\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\)
- 최대공약수의 성질에 의해 \((ab,p)=1\)이므로, 지수법칙에 의해 [math]\displaystyle{ \left(\frac{ab}{p}\right)=(ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) }[/math]이므로 원하는 결론을 얻는다. 여기서 르장드르 기호는 완전 곱셈적 함수임을 알 수 있다. 좀 더 엄밀히 표현하면, [math]\displaystyle{ L:{\mathbb{F}_p}^\times\to\left\{\pm1\right\} }[/math]가 완전 곱셈적 함수인 것.
한 예로, \(\left(\frac{860}{103}\right)\)의 값을 구해 보자. 103은 소수이고,
- [math]\displaystyle{ 860=8\cdot 103 + 36 }[/math]
이므로 \(860 \equiv 36 \pmod{103}\)이다. 따라서
- [math]\displaystyle{ \left(\frac{860}{103}\right)=\left(\frac{36}{103}\right) }[/math]
이다. 그런데 \(36=6^2\)이므로
- [math]\displaystyle{ \left(\frac{860}{103}\right)=\left(\frac{36}{103}\right)=1 }[/math]
임을 알 수 있다.
오일러 판정법
오일러의 규준이라고도 부른다.
- [math]\displaystyle{ \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \pmod p }[/math]
- [math]\displaystyle{ x_1,\ldots. x_{\frac{p-1}{2}} }[/math]를 법 \(p\)의 이차잉여라 하자. [math]\displaystyle{ a }[/math]가 이차잉여인 경우 [math]\displaystyle{ \{ax_1,\ldots, ax_{\frac{p-1}{2}} \} }[/math]는 집합으로서 [math]\displaystyle{ \{x_1,\ldots, x_{\frac{p-1}{2}} \} }[/math] 와 일치할 것이다. 따라서 모든 원소의 곱도 일치하고, [math]\displaystyle{ a^{\frac{p-1}{2}} x_1\cdots x_{\frac{p-1}{2}} \equiv x_1\cdots x_{\frac{p-1}{2}} \pmod{p} }[/math]가 성립한다. 양변을 소거하면 오일러의 규준을 얻는다.
- [math]\displaystyle{ a }[/math] 가 이차잉여가 아닐 경우, [math]\displaystyle{ ax_i }[/math] 들 또한 이차잉여가 아닐 것이고, 마찬가지로 [math]\displaystyle{ ax_i^{-1} }[/math] 또한 이차잉여가 아닐 것이다. 따라서 [math]\displaystyle{ \{x_1,\ldots, x_{\frac{p-1}{2}} \} \cup \{ax_1^{-1} ,\ldots, ax_{\frac{p-1}{2}} ^{-1} \} = \{1,2,\ldots, p-1\} }[/math] 이다. 모든 원소의 곱을 비교하면 [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv (p-1)! \equiv -1 \pmod p }[/math] 를 얻는다. 여기서 마지막 등호는 윌슨의 정리의 결과이다.
오일러 판정법을 사용해 다음을 보일 수 있다.
- [math]\displaystyle{ \left(\frac{-1}{p}\right)=\begin{cases}
1,&\text{if }p\equiv 1\pmod 4\\
-1,&\text{if }p\equiv -1\pmod 4
\end{cases} }[/math]
- 오일러의 규준에 의해 [math]\displaystyle{ \left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}\pmod p }[/math]인데 [math]\displaystyle{ \left(\frac{-1}{p}\right)=\pm 1 }[/math]이므로 [math]\displaystyle{ \left(\frac{-1}{p}\right)= (-1)^{\frac{p-1}{2}} }[/math]이다. \(p\)는 홀수이므로 \(4k+1\) 또는 \(4k-1\) 꼴인데, \((-1)^{2k}=1\)이고 \((-1)^{2k-1}=-1\)이므로 원하는 결론을 얻는다.
가우스 판정법
- \(a,\,2a,\,\ldots,\,\left(\frac{p-1}{2}\right)a\)를 법 \(p\)에 관해서 최소 양수 나머지로 바꾸자. 저 중에 \(\frac{p}{2}\)보다 큰 수의 개수를 \(s\)라 할 때, \(\left(\frac{a}{p}\right)=\left(-1\right)^s\)이다.
- [math]\displaystyle{ u_1,\,u_2,\,\ldots,\,u_s }[/math]를 [math]\displaystyle{ \frac{p}{2} }[/math]보다 큰 최소 양수 나머지라 하자. 그리고 [math]\displaystyle{ v_1,\,v_2,\,\ldots,\,v_t }[/math]를 [math]\displaystyle{ \frac{p}{2} }[/math]보다 작은 최소 양수 나머지라 하자. 먼저, [math]\displaystyle{ \left\{v_1,\,\ldots,\,v_t,\,p-u_1,\,\ldots,\,p-u_s\right\}=\left\{1,\,2,\,\ldots,\,\frac{p-1}{2}\right\} }[/math]임을 보일 것이다.
- 먼저, 모든 원소는 1에서 \(\frac{p-1}{2}\)사이.
- 총 \(\frac{p-1}{2}\)개의 원소가 있다.
- 만약 [math]\displaystyle{ v_i\equiv v_j\pmod p }[/math]이면, 적당한 정수 \(n,\,m\)에 대해 [math]\displaystyle{ na\equiv ma\pmod p }[/math]이다. 그런데 [math]\displaystyle{ \gcd\left(a,p\right)=1 }[/math]이므로 [math]\displaystyle{ n\equiv m\pmod p }[/math]이다. 그런데 \(n,\,m\)은 1에서 \(\frac{p-1}{2}\)사이의 정수이므로, \(n=m\)이다. 비슷한 방법으로, [math]\displaystyle{ p-u_i\equiv p-u_j\pmod p }[/math]이면 \(i=j\)임을 보일 수 있다. 만약 [math]\displaystyle{ v_i\equiv p-u_j\pmod p }[/math]이면, 적당한 정수 \(n,\,m\)에 대해 [math]\displaystyle{ na\equiv-ma\pmod p }[/math]이다. 즉, [math]\displaystyle{ n+m\equiv0\pmod p }[/math] 그런데 \(n,\,m\)은 1에서 \(\frac{p-1}{2}\)사이의 정수이므로 이는 불가능하다.
- 위 세 명제를 합하면 원하는 결과를 얻는다. 따라서, [math]\displaystyle{ v_1\cdots v_t\left(p-u_1\right)\cdots\left(p-u_s\right)\equiv1\cdot2\cdots\frac{p-1}{2}\pmod p }[/math]이고, 정리하면 [math]\displaystyle{ \left(-1\right)^sv_1\cdots v_t u_1\cdots u_s\equiv\left(\frac{p-1}{2}\right)!\pmod p }[/math]이다. 여기서 좌변은 [math]\displaystyle{ \left(-1\right)^sa^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)! }[/math]과 합동이고, [math]\displaystyle{ p\nmid\left(\frac{p-1}{2}\right)! }[/math]이므로 [math]\displaystyle{ \left(-1\right)^sa^{\frac{p-1}{2}}\equiv1\pmod p }[/math]이다. 따라서, 위 오일러 판정법에 의해 [math]\displaystyle{ \left(-1\right)^s\equiv a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\pmod p }[/math].
- [math]\displaystyle{ u_1,\,u_2,\,\ldots,\,u_s }[/math]를 [math]\displaystyle{ \frac{p}{2} }[/math]보다 큰 최소 양수 나머지라 하자. 그리고 [math]\displaystyle{ v_1,\,v_2,\,\ldots,\,v_t }[/math]를 [math]\displaystyle{ \frac{p}{2} }[/math]보다 작은 최소 양수 나머지라 하자. 먼저, [math]\displaystyle{ \left\{v_1,\,\ldots,\,v_t,\,p-u_1,\,\ldots,\,p-u_s\right\}=\left\{1,\,2,\,\ldots,\,\frac{p-1}{2}\right\} }[/math]임을 보일 것이다.
한 예시를 통해 가우스 판정법이 어떻게 쓰이는지 확인해 보자. 만약 [math]\displaystyle{ a=5,\,p=11 }[/math]이면, \(\frac{p-1}{2}=5\)이고, [math]\displaystyle{ \left\{a,2a,3a,4a,5a\right\}=\left\{5,10,15,20,25\right\} }[/math]를 법 11에 관한 최소 양수 나머지로 바꾸면 [math]\displaystyle{ \left\{5,11,4,9,3\right\} }[/math]이다. 이중 \(\frac{p-1}{2}=5.5\)보다 큰 수의 개수는 2이다. 따라서, \(s=2\)이고, \(\left(\frac{5}{11}\right)\equiv\left(-1\right)^s\equiv1\pmod p\)이다.
가우스 판정법을 사용하면 2가 어떨 때 이차잉여인지 확인할 수 있다.
- [math]\displaystyle{ \left\{2,2\cdot2,\cdots,\frac{p-1}{2}\cdot2\right\} }[/math]는 법 \(p\)에 대해 이미 최소 양수 나머지이다. 또한, [math]\displaystyle{ i\cdot2\lt \frac{p}{2} }[/math]이기 위한 조건은 [math]\displaystyle{ i\lt \frac{p}{4} }[/math]인 것이다. 즉, [math]\displaystyle{ s=\frac{p-1}{2}-\left\lfloor\frac{p}{4}\right\rfloor }[/math]. 따라서, [math]\displaystyle{ \left(\frac{2}{p}\right)=\left(-1\right)^{\frac{p-1}{2}-\left\lfloor\frac{p}{4}\right\rfloor} }[/math]. 만약 [math]\displaystyle{ p\equiv\pm1\pmod8 }[/math]이면, 직접 계산을 통해 [math]\displaystyle{ \left(\frac{2}{p}\right)=1 }[/math]임을 확인할 수 있다. 만약 [math]\displaystyle{ p\equiv\pm3\pmod8 }[/math]이면, 마찬가지로 [math]\displaystyle{ \left(\frac{2}{p}\right)=-1 }[/math]임을 확인할 수 있다. 정리하면 다음과 같다.
- [math]\displaystyle{ \left(\frac{2}{p}\right)=\begin{cases} 1,&\text{if }p\equiv \pm 1\pmod 8\\ -1,&\text{if }p\equiv \pm 3\pmod 8 \end{cases} }[/math]
위 두 조건을 하나로 합치면, [math]\displaystyle{ \left(\frac{2}{p}\right)=\left(-1\right)^{\frac{p^2-1}{8}} }[/math]이다. 증명은 생략.
이차상반성
\(p,\,q\)가 서로 다른 홀수인 소수일 때,
- \(\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\)
레온하르트 오일러가 1700년대 중반에 추측했던 내용. 정확히 말하면, 오일러는 \(p\)가 어떨 때 \(q\)의 이차잉여인지 확인하고자 했다. 오일러는 직접 수를 대입하여 확인하는 방법으로 이차잉여의 조건을 추측했고, 그 추측은 1785년에 르장드르에 의해 사실로 밝혀졌다. 르장드르는 오일러의 추측을 수식으로 표현했는데, 그게 바로 위에 있는 식. 르장드르는 이차상반성의 증명을 몇가지 출판하였으나, 르장드르의 증명은 전부 하나씩 뭔가 빠진, 불완전한 증명이었다. 완전한 증명은 1796년에 카를 프리드리히 가우스에 의해 발표되었고, 가우스의 나이는 고작 18살 이었다! 가우스 왈,
“ 내가 증명을 시도하는 1년 내내 이 정리가 나를 괴롭혔고, 나는 엄청난 노력을 쏟아 부었다. “
가우스는 여기서 멈추지 않고 총 6개의 서로 다른 증명법을 발견해낸다. 사실, 가우스의 궁극적 목표는 삼차잉여와 사차잉여의 조건을 찾는 것이었고, 이차상반성의 증명은 부록같은 느낌. 현재는 수많은 증명법이 알려져 있으며, 그 중에는 코시, 데데킨트, 디리클레, 크로네커, 아이젠슈타인 등, 수학을 한다면 한 번씩은 다 들어봤을 인물들의 증명이 있다. 2010년 초에는 233개의 다른 증명이 있다.
증명
활용
- 만약 \(\frac{p-1}{2}\)나 \(\frac{q-1}{2}\)가 짝수면, \(\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=1\)이다. 이는 곧 \(p\equiv1\pmod4\)나 \(q\equiv1\pmod4\)와 동치이다.
- 만약 \(p\equiv q\equiv3\pmod4\)이면, \(\frac{p-1}{2}\)와 \(\frac{q-1}{2}\)는 홀수이고, 따라서 \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=-1\)이다.
위 두 조건을 잘 정리하면 다음을 얻을 수 있다.
- [math]\displaystyle{ \left(\frac{q}{p}\right)=\begin{cases}\left(\frac{p}{q}\right),&\text{if }p\equiv1\pmod4\text{ or }q\equiv1\pmod4\\-\left(\frac{p}{q}\right),&\text{if }p\equiv q\equiv3\pmod4\end{cases} }[/math]
위 성질을 활용하면 3이 이차잉여일 조건을 확인할 수 있다. 먼저 \(p\geq5\)인 소수라 가정하자.
- \(p\)가 홀수인 소수이므로, [math]\displaystyle{ p\not\equiv0,\,2,\,4,\,6,\,8,\,10\pmod{12} }[/math]. 또한, \(p\neq3\)이므로, [math]\displaystyle{ p\not\equiv3,\,6,\,9\pmod{12} }[/math]이다. 즉, [math]\displaystyle{ p\equiv1,5,7,11\pmod{12} }[/math].
- [math]\displaystyle{ p\equiv1\pmod{12} }[/math]: [math]\displaystyle{ p\equiv1\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv1\pmod3 }[/math]이다. 따라서, 1번에 의해 \(\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=\left(\frac{1}{3}\right)=1\).
- [math]\displaystyle{ p\equiv5\pmod{12} }[/math]: [math]\displaystyle{ p\equiv1\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv2\pmod3 }[/math]이다. 따라서, 1번에 의해 \(\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=\left(\frac{2}{3}\right)=-1\).
- [math]\displaystyle{ p\equiv7\pmod{12} }[/math]: [math]\displaystyle{ p\equiv3\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv1\pmod3 }[/math]이다. 따라서, 2번에 의해 \(\left(\frac{3}{p}\right)=-\left(\frac{p}{3}\right)=-\left(\frac{1}{3}\right)=-1\).
- [math]\displaystyle{ p\equiv11\pmod{12} }[/math]: [math]\displaystyle{ p\equiv3\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv2\pmod3 }[/math]이다. 따라서, 2번에 의해 \(\left(\frac{3}{p}\right)=-\left(\frac{p}{3}\right)=-\left(\frac{2}{3}\right)=1\).
- 이를 정리하면,
- [math]\displaystyle{ \left(\frac{3}{p}\right)=\begin{cases} 1,&\text{if }p\equiv \pm 1\pmod{12}\\ -1,&\text{if }p\equiv \pm 5\pmod{12}\\ \end{cases} }[/math]
가우스 판정법과 이차상반성을 조합하면 6이 이차잉여일 조건도 확인할 수 있다. \(\left(\frac{6}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{3}{p}\right)\)임을 활용하여 적절히 케이스를 나눠주면, \(p\geq5\)인 소수일 때
- [math]\displaystyle{ \left(\frac{6}{p}\right)=\begin{cases}1,&\text{if }p\equiv\pm1,\,\pm5\pmod{24}\\-1,&\text{if }p\equiv\pm7,\,\pm11\pmod{24}\end{cases} }[/math]
이다. 증명은 생략한다.