二次相互法則 / Law of Quadratic Reciprocity
이차 잉여를 계산하는 방법 중 하나로, 오일러가 처음 제시하였고 가우스가 증명했다.
목차
1. 진술
2. 증명
2.1. 증명 1
2.1.1. 보조정리
2.1.2. 증명
2.2. 증명 2
2.2.1. 보조정리
2.2.2. 증명
2.3. 증명 3
3. 영상
홀수인 소수 p \neq q에 대하여 (p|q)(q|p)=(-1)^{\frac{(p-1)(q-1)}{4}}이다.
다음 보조정리를 증명하자.
홀수인 소수 p,q와 a \in \Bbb{Z}\ ((a,p)=(a,q)=1)에 대하여 q \equiv \pm p\ (\text{mod}\ 4a)이면 (a|p)=(a|q)이다.
가우스의 보조정리에 의해 다음을 증명하는 것으로 충분하다.
\{ak\ \text{mod}\ p\ |\ k=1,2,\cdots,\frac{p-1}{2}\}의 원소 중 \frac{p}{2}보다 큰 것의 개수를 s, \{ak\ \text{mod}\ q\ |\ k=1,2,\cdots,\frac{q-1}{2}\}의 원소 중 \frac{q}{2}보다 큰 것의 개수를 t이라 하면, s \equiv t\ (\text{mod}\ 2)이다.
우선
s가 얼마인지 구해보자.
n \in \Bbb{N}에 대하여
n\ \text{mod}\ p > \frac{p}{2}이려면 다음을 만족해야 한다.
n \in \bigcup_{i=1}^{\infty} \left(\frac{2i-1}{2}p,ip\right)여기서
n=ak<\frac{ap}{2}이므로
ak \in \bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{2i-1}{2}p,ip\right)가 된다. 즉
k \in \bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right)를 얻는다. 이 때
s는
\bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right)에 포함된 정수의 개수이다.
같은 방법으로
t는
\bigcup_{i=1}^{[\frac{a}{2}]} \left(\frac{(2i-1)q}{2a},\frac{iq}{a}\right)에 포함된 정수의 개수이다. 이제
s와
t의 기우성이 같음을 보이자. 이를 위해
\forall i \in [1,[\frac{a}{2}]]에 대해
\left(\frac{(2i-1)p}{2a},\frac{ip}{a}\right)와
\left(\frac{(2i-1)q}{2a},\frac{iq}{a}\right)에 포함된 정수의 개수의 기우성이 같음을 보일 것이다.
q \equiv p\ (\text{mod}\ 4a)인 경우를 보자. 그러면
q=p+4am인
m \in \Bbb{Z}가 존재한다.
\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)이므로 기우성이 같음을 확인할 수 있다.
q \equiv -p\ (\text{mod}\ 4a)인 경우에는
q=-p+4am인
m \in \Bbb{Z}가 존재하고,
\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)가 성립한다.
\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)이고
\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)이므로 기우성이 같음을 확인할 수 있다.
따라서 보조정리가 증명되었다.
이제 본 명제를 증명하자. 본 명제는 다음과 동치이다.
p \equiv 1\ (\text{mod}\ 4)이거나 q \equiv 1\ (\text{mod}\ 4)이면 (p|q)(q|p)=1, p \equiv q \equiv -1\ (\text{mod}\ 4)이면 (p|q)(q|p)=-1이다.
p \equiv q\ (\text{mod}\ 4)일 경우,
q=p+4m인
m \in \Bbb{Z},\ (m,p)=(m,q)=1가 존재한다. 그러면
(q|p)=(4m|p)=(m|p),\ (p|q)=(-4m|q)=(-1|q)(m|q)=(-1|q)(m|p)이므로
(p|q)(q|p)=(-1|q)이고, 이는
p \equiv 1\ (\text{mod}\ 4)일 때
1,
p \equiv -1\ (\text{mod}\ 4)일 때
-1이다.
p \not\equiv q\ (\text{mod}\ 4)일 경우,
q=-p+4m인
m \in \Bbb{Z},\ (m,p)=(m,q)=1가 존재한다. 그러면
(q|p)=(4m|p)=(m|p),\ (p|q)=(4m|q)=(m|q)=(m|p)이므로
(p|q)(q|p)=1이다.
따라서 본 명제가 증명되었다.
다음 보조정리를 증명하자.
홀소수
p에 대하여
p \nmid n일 때
\{nl\ \text{mod}\ p\ |\ l=1,2,\cdots,\frac{p-1}{2}\}의 원소 중
\frac{p}{2}보다 큰 것의 개수를
m이라 하자(즉, 이
m은
가우스의 보조정리에서 정의된
m이다). 이 때
m \equiv \sum_{i=1}^{\frac{p-1}{2}} \left[\frac{ni}{p}\right] + (n-1)\frac{p^2-1}{8}\ (\text{mod}\ 2)가 성립한다.
가우스의 보조정리를 증명할 때 썼던 정의들을 가져오자. 즉 \{n_i=ni\ \text{mod}\ p\ |\ i=1,2,\cdots,\frac{p-1}{2}\}에서 \frac{p}{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를 생각하자.
\sum_{i=1}^{\frac{p-1}{2}} n_i=\sum_{i=1}^{k} a_i+\sum_{i=1}^{m} b_i
A \cup C=\{1,2,\cdots,\frac{p-1}{2}\}이므로
\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}
두 식을 더하면
\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
n_i=ni-p\left[\frac{ni}{p}\right]이므로
\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}
\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)
이제 본 명제를 증명하자. 보조정리에 의해
(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)와
(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)를 얻는다.
집합 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}\}를 생각하자. 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]이므로
\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)
\therefore (p|q)(q|p)=(-1)^{\frac{(p-1)(q-1)}{4}}
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} 이라고 하자.
p와 서로소인 홀소수
q에 대해
\textup{(i)}\ \{g(1)\}^{q} = \{ \sum_{n=1}^{p-1}\left(\frac{n}{p}\right)\zeta^{n} \} ^{q}\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}= \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}= \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)
\textup{(ii)}\ \{g(1)\}^{q} = g(1)\cdot[\{g(1)\}^{2}]^{ \frac{q-1}{2} } = g(1)\cdot\{(-1)^{\frac{p-1}{2}}p\}^{ \frac{q-1}{2} } = g(1)\cdot(-1)^{\frac{p-1}{2}\frac{q-1}{2}}p^{ \frac{q-1}{2} } \equiv g(1)\cdot(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)\; (mod\; q)
\textup{(i), (ii)}에서
\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)\left(\frac{q}{p}\right) \equiv (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right) \; (mod\; q)\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) \equiv (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \; (mod\; q)\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\})
