이차 상호 법칙 (편집)

[[분류:가져온 문서/오메가]]
二次相互法則 / Law of Quadratic Reciprocity

[[이차 잉여]]를 계산하는 방법 중 하나로, 오일러가 처음 제시하였고 가우스가 증명했다.

== 진술 ==
홀수인 소수 [math(p \neq q)]에 대하여 [math((p|q)(q|p)=(-1)^{\frac{(p-1)(q-1)}{4}})]이다.

== 증명 ==
=== 증명 1 ===
다음 보조정리를 증명하자.

==== 보조정리 ====
홀수인 소수 [math(p,q)]와 [math(a \in \Bbb{Z}\ ((a,p)=(a,q)=1))]에 대하여 [math(q \equiv \pm p\ (\text{mod}\ 4a))]이면 [math((a|p)=(a|q))]이다.

==== 증명 ====
[[가우스의 보조정리]]에 의해 다음을 증명하는 것으로 충분하다.

>[math(\{ak\ \text{mod}\ p\ |\ k=1,2,\cdots,\frac{p-1}{2}\})]의 원소 중 [math(\frac{p}{2})]보다 큰 것의 개수를 [math(s)], [math(\{ak\ \text{mod}\ q\ |\ k=1,2,\cdots,\frac{q-1}{2}\})]의 원소 중 [math(\frac{q}{2})]보다 큰 것의 개수를 [math(t)]이라 하면, [math(s \equiv t\ (\text{mod}\ 2))]이다.

우선 [math(s)]가 얼마인지 구해보자. [math(n \in \Bbb{N})]에 대하여 [math(n\ \text{mod}\ p > \frac{p}{2})]이려면 다음을 만족해야 한다.

[math(n \in \bigcup_{i=1}^{\infty} \left(\frac{2i-1}{2}p,ip\right))]

여기서 [math(n=ak<\frac{ap}{2})]이므로 [math(ak \in \bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{2i-1}{2}p,ip\right))]가 된다. 즉 [math(k \in \bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right))]를 얻는다. 이 때 [math(s)]는 [math(\bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right))]에 포함된 정수의 개수이다.

같은 방법으로 [math(t)]는 [math(\bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{(2i-1)q}{2a},\frac{iq}{a}\right))]에 포함된 정수의 개수이다. 이제 [math(s)]와 [math(t)]의 기우성이 같음을 보이자. 이를 위해 [math(\forall i \in [1,[\frac{a}{2}]])]에 대해 [math(\left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right))]와 [math(\left(\frac{(2i-1)q}{2a},\frac{iq}{a}\right))]에 포함된 정수의 개수의 기우성이 같음을 보일 것이다.

[math(q \equiv p\ (\text{mod}\ 4a))]인 경우를 보자. 그러면 [math(q=p+4am)]인 [math(m \in \Bbb{Z})]가 존재한다. [math(\left(\frac{(2i-1)q}{2a},\frac{iq}{a}\right) = \left(2(2i-1)m+\frac{(2i-1)p}{2a},4im+\frac{ip}{a}\right))]이므로 기우성이 같음을 확인할 수 있다.

[math(q \equiv -p\ (\text{mod}\ 4a))]인 경우에는 [math(q=-p+4am)]인 [math(m \in \Bbb{Z})]가 존재하고, [math(\left(\frac{(2i-1)q}{2a},\frac{iq}{a}\right) = \left(2(2i-1)m-\frac{(2i-1)p}{2a},4im-\frac{ip}{a}\right))]가 성립한다.
[math(\left|\left(2(2i-1)m-\frac{(2i-1)p}{2a},4im-\frac{ip}{a}\right) \cap \Bbb{Z}\right| \equiv \left|\left(-2m-\frac{(2i-1)p}{2a},-\frac{ip}{a}\right) \cap \Bbb{Z}\right| \equiv \left|\left(\frac{ip}{a},2m+\frac{(2i-1)p}{2a}\right) \cap \Bbb{Z}\right|\ (\text{mod}\ 2))]이고
[math(\left|\left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right) \cap \Bbb{Z}\right|+\left|\left(\frac{ip}{a},2m+\frac{(2i-1)p}{2a}\right) \cap \Bbb{Z}\right|=\left|\left(\frac{(2i-1)p}{2a},2m+\frac{(2i-1)p}{2a}\right) \cap \Bbb{Z} \right| \equiv 0\ (\text{mod}\ 2))]이므로 기우성이 같음을 확인할 수 있다.

따라서 보조정리가 증명되었다.

이제 본 명제를 증명하자. 본 명제는 다음과 동치이다.

* [math(p \equiv 1\ (\text{mod}\ 4))]이거나 [math(q \equiv 1\ (\text{mod}\ 4))]이면 [math((p|q)(q|p)=1)], [math(p \equiv q \equiv -1\ (\text{mod}\ 4))]이면 [math((p|q)(q|p)=-1)]이다.

[math(p \equiv q\ (\text{mod}\ 4))]일 경우, [math(q=p+4m)]인 [math(m \in \Bbb{Z},\ (m,p)=(m,q)=1)]가 존재한다. 그러면 [math((q|p)=(4m|p)=(m|p),\ (p|q)=(-4m|q)=(-1|q)(m|q)=(-1|q)(m|p))]이므로 [math((p|q)(q|p)=(-1|q))]이고, 이는 [math(p \equiv 1\ (\text{mod}\ 4))]일 때 [math(1)], [math(p \equiv -1\ (\text{mod}\ 4))]일 때 [math(-1)]이다.

[math(p \not\equiv q\ (\text{mod}\ 4))]일 경우, [math(q=-p+4m)]인 [math(m \in \Bbb{Z},\ (m,p)=(m,q)=1)]가 존재한다. 그러면 [math((q|p)=(4m|p)=(m|p),\ (p|q)=(4m|q)=(m|q)=(m|p))]이므로 [math((p|q)(q|p)=1)]이다.

따라서 본 명제가 증명되었다.

=== 증명 2 ===
다음 보조정리를 증명하자.

==== 보조정리 ====
홀소수 [math(p)]에 대하여 [math(p \nmid n)]일 때 [math(\{nl\ \text{mod}\ p\ |\ l=1,2,\cdots,\frac{p-1}{2}\})]의 원소 중 [math(\frac{p}{2})]보다 큰 것의 개수를 [math(m)]이라 하자(즉, 이 [math(m)]은 [[가우스의 보조정리]]에서 정의된 [math(m)]이다). 이 때
[math(m \equiv \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{ni}{p}\right] + (n-1)\frac{p^2-1}{8}\ (\text{mod}\ 2))]

가 성립한다.

==== 증명 ====
가우스의 보조정리를 증명할 때 썼던 정의들을 가져오자. 즉 [math(\{n_i=ni\ \text{mod}\ p\ |\ i=1,2,\cdots,\frac{p-1}{2}\})]에서 [math(\frac{p}{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(\sum_{i=1}^{\frac{p-1}{2}} n_i=\sum_{i=1}^{k} a_i+\sum_{i=1}^{m} b_i)]
[math(A \cup C=\{1,2,\cdots,\frac{p-1}{2}\})]이므로
[math(\begin{aligned}
\sum_{i=1}^{\frac{p-1}{2}} i &= \sum_{i=1}^{k} a_i+\sum_{i=1}^{m} c_i \\
&= \sum_{i=1}^{k} a_i+pm-\sum_{i=1}^{m} b_i
\end{aligned})]
두 식을 더하면
[math(\sum_{i=1}^{\frac{p-1}{2}} n_i+\sum_{i=1}^{\frac{p-1}{2}} i=2\sum_{i=1}^{k} a_i+pm)]
[math(n_i=ni-p\left[\frac{ni}{p}\right])]이므로
[math(\begin{aligned}m \equiv mp &\equiv \sum_{i=1}^{\frac{p-1}{2}} n_i+\sum_{i=1}^{\frac{p-1}{2}} i \\&\equiv \sum_{i=1}^{\frac{p-1}{2}} (ni-p\left[\frac{ni}{p}\right])+\sum_{i=1}^{\frac{p-1}{2}} i \\&\equiv -p\sum_{i=1}^{\frac{p-1}{2}} \left[\frac{ni}{p}\right]+(n+1)\frac{p^2-1}{8}\\&\equiv \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{ni}{p}\right]+(n+1)\frac{p^2-1}{8}\ (\text{mod}\ 2)
\end{aligned})]
[math(\therefore m \equiv \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{ni}{p}\right] + (n-1)\frac{p^2-1}{8}\ (\text{mod}\ 2))]

이제 본 명제를 증명하자. 보조정리에 의해
[math((p|q)=(-1)^s,\ s \equiv \sum_{i=1}^{\frac{q-1}{2}} \left[\frac{pi}{q}\right] + (p-1)\frac{q^2-1}{8} \equiv \sum_{i=1}^{\frac{q-1}{2}} \left[\frac{pi}{q}\right]\ (\text{mod}\ 2))]와
[math((q|p)=(-1)^t,\ t \equiv \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{qi}{p}\right] + (q-1)\frac{p^2-1}{8} \equiv \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{qi}{p}\right]\ (\text{mod}\ 2))]를 얻는다.

집합 [math(K=\{xp-yq \mid x \in \left[1,\frac{q-1}{2}\right] \cap \Bbb{Z},\ y \in \left[1,\frac{p-1}{2}\right] \cap \Bbb{Z}\})]를 생각하자. [math(K \subset \Bbb{Z} \setminus \{0\},\ |K|=\frac{(p-1)(q-1)}{4},\ |K \cap \Bbb{Z}^{+}|=\sum_{x=1}^{\frac{q-1}{2}} \left[\frac{xp}{q}\right],\ |K \cap \Bbb{Z}^{-}|=\sum_{y=1}^{\frac{p-1}{2}} \left[\frac{yq}{p}\right])]이므로
[math(\frac{(p-1)(q-1)}{4}=\sum_{i=1}^{\frac{q-1}{2}} \left[\frac{pi}{q}\right]+ \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{qi}{p}\right] \equiv s+t\ (\text{mod}\ 2))]
[math(\therefore (p|q)(q|p)=(-1)^{\frac{(p-1)(q-1)}{4}})]

=== 증명 3 ===
<math>g(a) = \zeta^{a\cdot0^{2}}+\zeta^{a\cdot1^{2}}+...+\zeta^{a(p-1)^{2}} =\sum_{n=1}^{p-1}\left(\frac{n}{p}\right)\zeta^{an} </math> 이라고 하자. <math>p</math>와 서로소인 홀소수 <math>q</math>에 대해

<math>\textup{(i)}\ \{g(1)\}^{q} =  \{ \sum_{n=1}^{p-1}\left(\frac{n}{p}\right)\zeta^{n} \} ^{q}</math>
* <math> \equiv  \sum_{n=1}^{p-1}\{\left(\frac{n}{p}\right)\zeta^{n}\} ^{q} =  \sum_{n=1}^{p-1}\left(\frac{n}{p}\right) ^{q}\zeta^{nq} =  \sum_{n=1}^{p-1}\left(\frac{n}{p}\right) \zeta^{nq} </math>
* <math>= \sum_{n=1}^{p-1}\left(\frac{q}{p}\right)\left(\frac{q}{p}\right)\left(\frac{n}{p}\right) \zeta^{nq} =  \left(\frac{q}{p}\right)\sum_{n=1}^{p-1}\left(\frac{nq}{p}\right)\zeta^{nq}</math>
* <math>=  \left(\frac{q}{p}\right)\sum_{l=1}^{p-1}\left(\frac{l}{p}\right)\zeta^{l} =  \left(\frac{q}{p}\right)g(1) \;  (mod\; q)</math>

<math>\textup{(ii)}\ \{g(1)\}^{q} =  g(1)\cdot[\{g(1)\}^{2}]^{ \frac{q-1}{2} }</math> 
* <math> =  g(1)\cdot\{(-1)^{\frac{p-1}{2}}p\}^{ \frac{q-1}{2} }</math> 
* <math> =  g(1)\cdot(-1)^{\frac{p-1}{2}\frac{q-1}{2}}p^{ \frac{q-1}{2} }</math> 
* <math> \equiv  g(1)\cdot(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)\;  (mod\; q)</math>

<math>\textup{(i), (ii)}</math>에서

<math>\left(\frac{q}{p}\right)g(1)  \equiv  g(1)\cdot(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right) \;  (mod\; q)  </math>

<math> \left(\frac{q}{p}\right)  \equiv  (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right) \;  (mod\; q)  </math>

<math> \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)  \equiv  (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \;  (mod\; q)  </math>

* <math> \therefore \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\;  \;  (\because  \left(\frac{p}{q}\right), \left(\frac{q}{p}\right), (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \in \{1, -1\})</math>

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

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

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

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