개요[편집 | 원본 편집]
[math]\displaystyle{ p,\,q }[/math]가 서로 다른 홀수인 소수일 때,
- [math]\displaystyle{ \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}} }[/math]
이때 [math]\displaystyle{ \left(\frac{q}{p}\right) }[/math]는 르장드르 기호이다.
역사[편집 | 원본 편집]
레온하르트 오일러가 1700년대 중반에 추측했던 내용. 정확히 말하면, 오일러는 [math]\displaystyle{ p }[/math]가 어떨 때 [math]\displaystyle{ q }[/math]의 이차잉여인지 확인하고자 했다. 오일러는 직접 수를 대입하여 확인하는 방법으로 이차잉여의 조건을 추측했고, 그 추측은 1785년에 르장드르에 의해 사실로 밝혀졌다. 르장드르는 오일러의 추측을 수식으로 표현했는데, 그게 바로 위에 있는 식. 르장드르는 이차상반성의 증명을 몇가지 출판하였으나, 르장드르의 증명은 전부 하나씩 뭔가 빠진, 불완전한 증명이었다. 완전한 증명은 1796년에 카를 프리드리히 가우스에 의해 발표되었고, 가우스의 나이는 고작 18살 이었다! 가우스 왈,
“ 내가 증명을 시도하는 1년 내내 이 정리가 나를 괴롭혔고, 나는 엄청난 노력을 쏟아 부었다. “
가우스는 여기서 멈추지 않고 총 6개의 서로 다른 증명법을 발견해낸다. 사실, 가우스의 궁극적 목표는 삼차잉여와 사차잉여의 조건을 찾는 것이었고, 이차상반성의 증명은 부록같은 느낌. 현재는 수많은 증명법이 알려져 있으며, 그 중에는 코시, 데데킨트, 디리클레, 크로네커, 아이젠슈타인 등, 수학을 한다면 한 번씩은 다 들어봤을 인물들의 증명이 있다. 2010년 초에는 233개의 다른 증명이 있다.
증명[편집 | 원본 편집]
아이젠슈타인의 증명을 소개한다. 사실,가우스의 3번째 증명을 간략화 한 버전이다.
- 도움정리: [math]\displaystyle{ p }[/math]가 홀수인 소수이고 [math]\displaystyle{ a }[/math]가 [math]\displaystyle{ p }[/math]와 서로소인 홀수인 정수일 때, [math]\displaystyle{ \left(\frac{a}{p}\right)=\left(-1\right)^{T\left(a,p\right)} }[/math]이다. 단, [math]\displaystyle{ T\left(a,p\right)=\sum_{j=1}^{\left(p-1\right)/2}\left\lfloor ja/p\right\rfloor }[/math]
- [math]\displaystyle{ a,\,2a,\ldots,\frac{p-1}{2}a }[/math]를 법 [math]\displaystyle{ p }[/math]에 대해 최소 양수 나머지로 치환하자. 그 중, [math]\displaystyle{ u_1,\,u_2,\ldots,u_s }[/math]를 [math]\displaystyle{ p/2 }[/math]보다 큰 나머지, [math]\displaystyle{ v_1,\,v_2,\ldots,v_t }[/math]를 [math]\displaystyle{ p/2 }[/math]보다 작은 나머지라 하자. 나눗셈 정리에 의해,
- [math]\displaystyle{ ja=p\left\lfloor ja/p\right\rfloor+r\quad\cdots1 }[/math] ([math]\displaystyle{ r }[/math]은 나머지)
- 여기서 나머지 [math]\displaystyle{ r }[/math]은 필연적으로 [math]\displaystyle{ u_i }[/math]나 [math]\displaystyle{ v_i }[/math]중 하나이다 (지표까지 같을 필요는 없다). 한편, [math]\displaystyle{ \left\{ja\mid1\leq j\leq p\right\} }[/math]는 법 [math]\displaystyle{ p }[/math]에 대한 완전잉여계를 구성하므로, 각 원소는 서로 다르다. 따라서, 1번 식을 쭉 더하면,
- [math]\displaystyle{ \sum_{j=1}^{\left(p-1\right)/2}ja=\sum_{j=1}^{\left(p-1\right)/2}p\left\lfloor ja/p\right\rfloor+\sum_{j=1}^su_j+\sum_{j=1}^tv_j\quad\cdots2 }[/math]
- 한편, 가우스 판정법을 증명하는 과정 중, [math]\displaystyle{ p-u_1,\ldots,p-u_s,\,v_1,\ldots,v_t }[/math]는 [math]\displaystyle{ 1,\,2,\ldots,\left(p-1\right)/2 }[/math]과 일치함을 보였다 (순서는 다를 수도 있다). 이 수들을 다 더하면,
- [math]\displaystyle{ \sum_{j=1}^{\left(p-1\right)/2}j=\sum_{j=1}^s\left(p-u_j\right)+\sum_{j=1}^tv_j=ps-\sum_{j=1}^su_j+\sum_{j=1}^tv_j\quad\cdots3 }[/math]
- 3번 식에서 2번 식을 빼면,
- [math]\displaystyle{ \sum_{j=1}^{\left(p-1\right)/2}ja-\sum_{j=1}^{\left(p-1\right)/2}j=\sum_{j=1}^{\left(p-1\right)/2}p\left\lfloor ja/p\right\rfloor-ps+2\sum_{j=1}^su_j\quad\cdots4 }[/math]
- 한편, [math]\displaystyle{ T\left(a,p\right)=\sum_{j=1}^{\left(p-1\right)/2}\left\lfloor ja/p\right\rfloor }[/math]이므로, 4번 식은
- [math]\displaystyle{ \left(a-1\right)\sum_{j=1}^{\left(p-1\right)/2}j=pT\left(a,p\right)-ps+2\sum_{j=1}^su_j\quad\cdots5 }[/math]
- 5번 식의 양변을 법 2에 대해 계산하면, [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ p }[/math]가 홀수이므로, [math]\displaystyle{ pT\left(a,p\right)\equiv ps\pmod2 }[/math]이고, 곧 [math]\displaystyle{ T\left(a,p\right)\equiv s\pmod2 }[/math]이다. 한편, 가우스 판정법에서, [math]\displaystyle{ \left(-1\right)^s=\left(\frac{a}{p}\right) }[/math]이다. 그런데 [math]\displaystyle{ \left(-1\right)^s=\left(-1\right)^{T\left(a,p\right)} }[/math]이므로, [math]\displaystyle{ \left(\frac{a}{p}\right)=\left(-1\right)^{T\left(a,p\right)} }[/math]이다.
- 본 증명
- [math]\displaystyle{ 1\leq x\leq\left(p-1\right)/2,\,1\leq y\leq\left(q-1\right)/2 }[/math]라 하자. 그럼, 총 [math]\displaystyle{ \frac{p-1}{2}\cdot\frac{q-1}{2} }[/math]쌍의 [math]\displaystyle{ \left(x,y\right) }[/math]가 있다. 만약 [math]\displaystyle{ qx=py }[/math]이면, [math]\displaystyle{ q\mid py }[/math]이고, [math]\displaystyle{ q }[/math]는 소수이므로 [math]\displaystyle{ q\mid p }[/math]이거나 [math]\displaystyle{ q\mid y }[/math]이다. 그런데 [math]\displaystyle{ p }[/math]와 [math]\displaystyle{ q }[/math]는 서로 다른 소수이므로 [math]\displaystyle{ q\not\mid p }[/math]이고, [math]\displaystyle{ 1\leq y\leq\left(q-1\right)/2 }[/math]이므로 [math]\displaystyle{ q\not\mid y }[/math]이다. 따라서, [math]\displaystyle{ qx\neq py }[/math]이다. 먼저, [math]\displaystyle{ qx\gt qy }[/math]를 만족하는 순서쌍의 개수를 세어보자. 이 조건을 만족하기 위해서는, [math]\displaystyle{ 1\leq x\leq\left(p-1\right)/2 }[/math]이고 [math]\displaystyle{ 1\leq y\leq qx/p }[/math]이어야 한다. 따라서, 각 [math]\displaystyle{ x }[/math]값에 대해 [math]\displaystyle{ \left\lfloor qx/p\right\rfloor }[/math]개의 [math]\displaystyle{ y }[/math]값이 존재한다. 즉, 조건을 만족하는 순서쌍의 개수는 [math]\displaystyle{ \sum_{j=1}^{\left(p-1\right)/2}\left\lfloor qj/p\right\rfloor }[/math]. 비슷한 방법으로, [math]\displaystyle{ qx\lt py }[/math]를 만족하는 순서쌍의 개수는 [math]\displaystyle{ \sum_{j=1}^{\left(q-1\right)/2}\left\lfloor pj/q\right\rfloor }[/math]임을 보일 수 있다. 저 두 값을 전부 더하면,
- [math]\displaystyle{ \sum_{j=1}^{\left(p-1\right)/2}\left\lfloor qj/p\right\rfloor+\sum_{j=1}^{\left(q-1\right)/2}\left\lfloor pj/q\right\rfloor=\frac{p-1}{2}\cdot\frac{q-1}{2} }[/math]
- 한편, 위 식은,
- [math]\displaystyle{ T\left(q,p\right)+T\left(p,q\right)=\frac{p-1}{2}\cdot\frac{q-1}{2} }[/math]
- 과 동치이고, 따라서,
- [math]\displaystyle{ \left(-1\right)^{T\left(q,p\right)+T\left(p,q\right)}=\left(-1\right)^{T\left(q,p\right)}\left(-1\right)^{T\left(p,q\right)}=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} }[/math]
- 이다. 도움정리를 사용하면, [math]\displaystyle{ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} }[/math]이다.
활용[편집 | 원본 편집]
- 만약 [math]\displaystyle{ \frac{p-1}{2} }[/math]나 [math]\displaystyle{ \frac{q-1}{2} }[/math]가 짝수면, [math]\displaystyle{ \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=1 }[/math]이다. 이는 곧 [math]\displaystyle{ p\equiv1\pmod4 }[/math]나 [math]\displaystyle{ q\equiv1\pmod4 }[/math]와 동치이다.
- 만약 [math]\displaystyle{ p\equiv q\equiv3\pmod4 }[/math]이면, [math]\displaystyle{ \frac{p-1}{2} }[/math]와 [math]\displaystyle{ \frac{q-1}{2} }[/math]는 홀수이고, 따라서 [math]\displaystyle{ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=-1 }[/math]이다.
위 두 조건을 잘 정리하면 다음을 얻을 수 있다.
- [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이 이차잉여일 조건을 확인할 수 있다. 먼저 [math]\displaystyle{ p\geq5 }[/math]인 소수라 가정하자.
- [math]\displaystyle{ p }[/math]가 홀수인 소수이므로, [math]\displaystyle{ p\not\equiv0,\,2,\,4,\,6,\,8,\,10\pmod{12} }[/math]. 또한, [math]\displaystyle{ p\neq3 }[/math]이므로, [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번에 의해 [math]\displaystyle{ \left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=\left(\frac{1}{3}\right)=1 }[/math].
- [math]\displaystyle{ p\equiv5\pmod{12} }[/math]: [math]\displaystyle{ p\equiv1\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv2\pmod3 }[/math]이다. 따라서, 1번에 의해 [math]\displaystyle{ \left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=\left(\frac{2}{3}\right)=-1 }[/math].
- [math]\displaystyle{ p\equiv7\pmod{12} }[/math]: [math]\displaystyle{ p\equiv3\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv1\pmod3 }[/math]이다. 따라서, 2번에 의해 [math]\displaystyle{ \left(\frac{3}{p}\right)=-\left(\frac{p}{3}\right)=-\left(\frac{1}{3}\right)=-1 }[/math].
- [math]\displaystyle{ p\equiv11\pmod{12} }[/math]: [math]\displaystyle{ p\equiv3\pmod4 }[/math]이고 [math]\displaystyle{ p\equiv2\pmod3 }[/math]이다. 따라서, 2번에 의해 [math]\displaystyle{ \left(\frac{3}{p}\right)=-\left(\frac{p}{3}\right)=-\left(\frac{2}{3}\right)=1 }[/math].
- 이를 정리하면,
- [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이 이차잉여일 조건도 확인할 수 있다. [math]\displaystyle{ \left(\frac{6}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{3}{p}\right) }[/math]임을 활용하여 적절히 케이스를 나눠주면, [math]\displaystyle{ p\geq5 }[/math]인 소수일 때
- [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]
이다. 증명은 생략한다.
대수적 정수로 확장[편집 | 원본 편집]
이 문단은 비어 있습니다. 내용을 추가해 주세요.