(+)분류 : 가져온 문서/오메가
가우스의 보조정리(Gauss' lemma)는 르장드르 기호를 계산하는 방법 중 하나이다. 오일러의 판정법보다 계산이 간단하다.
1. 진술 ✎ ⊖
홀소수 p에 대하여 p \\nmid n일 때 \\{nl\\ \\operatorname{mod} p\\ |\\ l=1,2,\\cdots,\\frac{p-1}{2}\\}의 원소 중 \\frac{p}{2}보다 큰 것의 개수를 m이라 하자. 이 때, (n|p)=(-1)^m이다.
2. 증명 ✎ ⊖
nl\\ (l=1,2,\\cdots,\\frac{p-1}{2})들은 각각 \\mathrm{mod}\\ p에 대해 합동이 아니다. \\{nl\\ \\operatorname{mod} p\\ |\\ l=1,2,\\cdots,\\frac{p-1}{2}\\}보다 작은 원소를 모은 집합을 A=\\{a_1,a_2,\\cdots,a_k\\}, 큰 원소를 모든 집합을 B=\\{b_1,b_2,\\cdots,b_m\\}라고 하자.
이제 C=\\{c_1,c_2,\\cdots,c_m\\},\\ c_i=p-b_i를 생각하자. 그러면 C의 원소들은 모두 \\frac{p}{2}보다 작다. 만약 a_i=c_j라면 a_i+b_j=p이므로 자연수 s,t \\in [1,\\frac{p}{2}]가 존재하여 sn+tn \\equiv a_i+b_j \\equiv 0\\ (\\mathrm{mod}\\ p)이다. 즉 (s+t)n \\equiv 0\\ (\\mathrm{mod}\\ p)인데, 0<s+t<p이고 p \\nmid n이므로 모순. 따라서 A와 C의 원소는 모두 다르다. 즉 A \\cup C=\\{1,2,\\cdots,\\frac{p-1}{2}\\}이다.
\\begin{aligned}\\left(\\frac{p-1}{2}\\right)! &= \\prod_{i=1}^{k} a_i \\prod_{i=1}^{m} c_i \\\\&\\equiv \\prod_{i=1}^{k} a_i \\prod_{i=1}^{m} (-b_i) \\\\&\\equiv (-1)^m \\prod_{i=1}^{\\frac{p-1}{2}} ni\\\\&\\equiv (-1)^m n^{\\frac{p-1}{2}} \\left(\\frac{p-1}{2}\\right)! \\pmod{p}\\\\\\end{aligned}
\\therefore (-1)^m=(n|p)
마지막에 오일러의 판정법을 이용한다.
이제 C=\\{c_1,c_2,\\cdots,c_m\\},\\ c_i=p-b_i를 생각하자. 그러면 C의 원소들은 모두 \\frac{p}{2}보다 작다. 만약 a_i=c_j라면 a_i+b_j=p이므로 자연수 s,t \\in [1,\\frac{p}{2}]가 존재하여 sn+tn \\equiv a_i+b_j \\equiv 0\\ (\\mathrm{mod}\\ p)이다. 즉 (s+t)n \\equiv 0\\ (\\mathrm{mod}\\ p)인데, 0<s+t<p이고 p \\nmid n이므로 모순. 따라서 A와 C의 원소는 모두 다르다. 즉 A \\cup C=\\{1,2,\\cdots,\\frac{p-1}{2}\\}이다.
\\begin{aligned}\\left(\\frac{p-1}{2}\\right)! &= \\prod_{i=1}^{k} a_i \\prod_{i=1}^{m} c_i \\\\&\\equiv \\prod_{i=1}^{k} a_i \\prod_{i=1}^{m} (-b_i) \\\\&\\equiv (-1)^m \\prod_{i=1}^{\\frac{p-1}{2}} ni\\\\&\\equiv (-1)^m n^{\\frac{p-1}{2}} \\left(\\frac{p-1}{2}\\right)! \\pmod{p}\\\\\\end{aligned}
\\therefore (-1)^m=(n|p)
마지막에 오일러의 판정법을 이용한다.
3. 예시 ✎ ⊖
p=23,n=17일 때
\\begin{aligned} \\{nl\\ \\mathrm{mod}\\ p &\\mid l=1,2,\\cdots,\\frac{p-1}{2}\\} \\\\&= \\{17 \\ \\mathrm{mod}\\ 23, 34 \\ \\mathrm{mod}\\ 23, 51 \\ \\mathrm{mod}\\ 23, 68 \\ \\mathrm{mod}\\ 23, 85 \\ \\mathrm{mod}\\ 23, 102 \\ \\mathrm{mod}\\ 23, 119 \\ \\mathrm{mod}\\ 23, 136 \\ \\mathrm{mod}\\ 23, 153 \\ \\mathrm{mod}\\ 23, 170 \\ \\mathrm{mod}\\ 23, 187 \\ \\mathrm{mod}\\ 23\\} \\\\&= \\{17, 11, 5, 22, 16, 10, 4, 21, 15, 9, 3\\} \\\\&= \\{3, 4, 5, 9, 10, 11, 15, 16, 17, 21, 22\\} \\end{aligned}
이므로 m=5, 즉 (17|23)=(-1)^5=-1이다.
\\begin{aligned} \\{nl\\ \\mathrm{mod}\\ p &\\mid l=1,2,\\cdots,\\frac{p-1}{2}\\} \\\\&= \\{17 \\ \\mathrm{mod}\\ 23, 34 \\ \\mathrm{mod}\\ 23, 51 \\ \\mathrm{mod}\\ 23, 68 \\ \\mathrm{mod}\\ 23, 85 \\ \\mathrm{mod}\\ 23, 102 \\ \\mathrm{mod}\\ 23, 119 \\ \\mathrm{mod}\\ 23, 136 \\ \\mathrm{mod}\\ 23, 153 \\ \\mathrm{mod}\\ 23, 170 \\ \\mathrm{mod}\\ 23, 187 \\ \\mathrm{mod}\\ 23\\} \\\\&= \\{17, 11, 5, 22, 16, 10, 4, 21, 15, 9, 3\\} \\\\&= \\{3, 4, 5, 9, 10, 11, 15, 16, 17, 21, 22\\} \\end{aligned}
이므로 m=5, 즉 (17|23)=(-1)^5=-1이다.
4. 사용 ✎ ⊖
르장드르 기호의 계산, 혹은 가우스 이차 상반법칙의 증명에 사용된다.
