(+)분류 : 가져온 문서/오메가
二次相互法則 / Law of Quadratic Reciprocity
이차 잉여를 계산하는 방법 중 하나로, 오일러가 처음 제시하였고 가우스가 증명했다.
1. 진술 ✎ ⊖
홀수인 소수 p \\neq q에 대하여 (p|q)(q|p)=(-1)^{\\frac{(p-1)(q-1)}{4}}이다.
2. 증명 ✎ ⊖
2.1. 증명 1 ✎ ⊖
다음 보조정리를 증명하자.
2.1.1. 보조정리 ✎ ⊖
홀수인 소수 p,q와 a \\in \\Bbb{Z}\\ ((a,p)=(a,q)=1)에 대하여 q \\equiv \\pm p\\ (\\text{mod}\\ 4a)이면 (a|p)=(a|q)이다.
2.1.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 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이다.
따라서 본 명제가 증명되었다.
\\{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이다.
따라서 본 명제가 증명되었다.
2.2. 증명 2 ✎ ⊖
다음 보조정리를 증명하자.
2.2.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)
가 성립한다.
m \\equiv \\sum_{i=1}^{\\frac{p-1}{2}} \\left[\\frac{ni}{p}\\right] + (n-1)\\frac{p^2-1}{8}\\ (\\text{mod}\\ 2)
가 성립한다.
2.2.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}}
\\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}}
2.3. 증명 3 ✎ ⊖
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}
\\textup{(ii)}\\ \\{g(1)\\}^{q} = g(1)\\cdot[\\{g(1)\\}^{2}]^{ \\frac{q-1}{2} }
\\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)
\\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\\})
