가우스의 보조정리(Gauss' lemma)는 르장드르 기호를 계산하는 방법 중 하나이다. 오일러의 판정법에서 지수 계산이 부담스러울 때, 단순히 개수만 세는 방식으로 문제를 치환해줘서 오일러의 판정법보다 계산이 간단하다.
(1)목차
1. 진술
2. 증명
3. 예시
4. 사용
5. 영상
홀소수 p에 대하여 p \nmid n일 때 \{nl\ \operatorname{mod} p\ |\ l=1,2,\cdots,\frac{p-1}{2}\}의 원소 중 \frac{p}{2}보다 큰 것의 개수를 m이라 하자. 이 때, (n|p)=(-1)^m이다.
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)
마지막에 오일러의 판정법을 이용한다.
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이다.
르장드르 기호의 계산, 혹은 가우스 이차 상반법칙의 증명에 사용된다.
