가우스의 보조정리 (편집)

[[분류:가져온 문서/오메가]]
'''가우스의 보조정리'''(Gauss' lemma)는 르장드르 기호를 계산하는 방법 중 하나이다. 오일러의 판정법보다 계산이 간단하다.

== 진술 ==
홀소수 [math(p)]에 대하여 [math(p \nmid n)]일 때 [math(\{nl\ \operatorname{mod} p\ |\ l=1,2,\cdots,\frac{p-1}{2}\})]의 원소 중 [math(\frac{p}{2})]보다 큰 것의 개수를 [math(m)]이라 하자. 이 때, [math((n|p)=(-1)^m)]이다.

== 증명 ==
[math(nl\ (l=1,2,\cdots,\frac{p-1}{2}))]들은 각각 [math(\mathrm{mod}\ p)]에 대해 합동이 아니다. [math(\{nl\ \operatorname{mod} p\ |\ l=1,2,\cdots,\frac{p-1}{2}\})]보다 작은 원소를 모은 집합을 [math(A=\{a_1,a_2,\cdots,a_k\})], 큰 원소를 모든 집합을 [math(B=\{b_1,b_2,\cdots,b_m\})]라고 하자.

이제 [math(C=\{c_1,c_2,\cdots,c_m\},\ c_i=p-b_i)]를 생각하자. 그러면 [math(C)]의 원소들은 모두 [math(\frac{p}{2})]보다 작다. 만약 [math(a_i=c_j)]라면 [math(a_i+b_j=p)]이므로 자연수 [math(s,t \in [1,\frac{p}{2}])]가 존재하여 [math(sn+tn \equiv a_i+b_j \equiv 0\ (\mathrm{mod}\ p))]이다. 즉 [math((s+t)n \equiv 0\ (\mathrm{mod}\ p))]인데, [math(0<s+t<p)]이고 [math(p \nmid n)]이므로 모순. 따라서 [math(A)]와 [math(C)]의 원소는 모두 다르다. 즉 [math(A \cup C=\{1,2,\cdots,\frac{p-1}{2}\})]이다.

[math(\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})]

[math(\therefore (-1)^m=(n|p))]

마지막에 오일러의 판정법을 이용한다.

== 예시 ==
[math(p=23,n=17)]일 때

[math(\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})]

이므로 [math(m=5)], 즉 [math((17|23)=(-1)^5=-1)]이다.

== 사용 ==
르장드르 기호의 계산, 혹은 가우스 이차 상반법칙의 증명에 사용된다.

== 영상 ==
[youtube(mT8nJWIvAp4)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)