📂정수론

가우스의 이차상호 법칙 증명

정리 ¹

서로 다른 두 홀수 소수 $p , q$ 에 대해 다음이 성립한다.

• (1): $$ \left( {{ q } \over { p }} \right) = \begin{cases} \left( {{ p } \over { q }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ p } \over { q }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} $$
• (2): $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$

(1)과 (2)는 표현만 다를 뿐 같은 말이다.

이차잉여에 대해 너무나 깔끔하게 정리되어 있어서 그 효용은 둘째치고서라도 수학적인 아름다움이 일품이다. 가우스는 처음으로 증명한 뒤로도 굉장히 이 법칙을 아껴서 평생에 걸쳐 8가지의 서로 다른 증명을 남겼다고 한다.

증명

전략: 본 포스트에선 조금 길고 세련되지는 않았지만 어려운 개념을 사용하지 않은 증명을 소개할 것이다. 가우스의 놀라운 아이디어가 핵심이며, 본격적인 증명에 앞서 간단하게 알아보도록 하자.

가우스의 아이디어: 소수 $p = 2n + 1$ 와 $1 \le x, x ' \le n$ 에 대해 $ax \equiv e_{x} x ' \pmod{p}$ 를 만족하도록 $e_{x} = \pm 1$ 이라 두면 $$ a^{{p-1} \over {2} } = a^{n} \equiv e_{1} e_{2} \cdots e_{n} \pmod{p} $$

예로써 $\pmod{11}$ 에서 이차잉여인 $a = 3$ 의 경우를 보면 $11 = 2n + 1 = 2 \cdot 5 +1$ 이므로 $n=5$ 다. 직접 $3^{5} 5!$ 를 계산해보자. $$ \begin{align*} 3^{5} 5! \equiv& (3 \cdot 1)(3 \cdot 2)(3 \cdot 3)(3 \cdot 4)(3 \cdot 1) \\ =& 3 \cdot 6 \cdot 9 \cdot 12 \cdot 15 \\ \equiv& 3 \cdot (-5) \cdot (-2) \cdot 1 \cdot 4 \pmod{11} \\ \equiv& (1 \cdot 3)(-1 \cdot 5)(-1 \cdot 2)(1 \cdot 1)(1 \cdot 4) \\ \equiv& (1 \cdot 1)(-1 \cdot 2)(1 \cdot 3)(1 \cdot 4)(-1 \cdot 5) \\ \equiv& (-1)^{2} 5! \pmod{11} \end{align*} $$ 양변을 $5!$ 로 나누면 $3^{5} \equiv (-1)^2 \equiv 1 \pmod{11}$ 을 얻는다. 이 아이디어가 경이로운 것은 때 $a$ 를 거듭제곱하고 $p$ 로 나누는 삽질을 $(-1)$ 을 세는 문제로 바꿀 수 있기 때문이다.

오일러 판정법: 소수 $p \ne 2$ 에 대해, $\displaystyle a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p}$

그 말인 즉슨 거듭제곱이 필요한 오일러 판정법을 더욱 편하게 쓸 수 있다는 것이다. 위 예시에서는, $$ 3^{{11- 1 } \over {2}} = 3^5 \equiv 1 \pmod{11} $$ 거듭제곱하고 $p$ 로 나눠서 나머지를 구하는 삽질이 너무나도 단순한 문제가 되었다.

---

두 소수 $p,q$ 를 다음과 같이 두자. $$ p := 2n +1 \\ q := 2m+1 $$ $1 \le x,x’ \le n$ 에 대해 $q x \equiv e_{x} x ' \pmod{p}$ 이고 합동의 정의에 따라 어떤 $y \in \mathbb{Z}$ 에 대해 $$ qx = e_{x} x ' + py $$ 와 같이 둘 수 있다. 우리는 $(-1)$ 을 카운트하는 것에 관심이 있으므로 $e_{x } = -1$ 인 경우만 신경쓰면 된다. 만약 $e_{x } = -1$ 이면 $qx = -x’ + py$ 이고, $y$ 에 대해 나타내면 $$ y = {{1} \over {p}} (qx + x ' ) >0 $$ 그리고 $\le x,x’ \le n$ 이고 $2n < p$ 이므로 $$ y = {{1} \over {p}} (qx + x ' ) \le {{(q+1)n} \over {p}} < {{q+1} \over {2}} = m+1 $$ 따라서 $1 \le y \le m$ 이다. 한편 가정에서 $1 \le x , x ' \le n$ 이었으므로 $1 \le x ' = py - qx \le n$ 이다. 다시 말해서, $e_{x} = -1$ 이라는 것은 $$ 1 \le x \le n \\ 1 \le y \le m \\ 1 \le py - qx \le n $$ 을 만족시키는 $y$ 가 존재한다는 것이다. 이제 다음과 같은 집합 $$ N : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , 1 \le py - qx \le n \right\} $$ 을 생각해보면 $$ \left( {{q} \over {p}} \right) \equiv q^{{p-1} \over {2}} = (-1 )^{|N|} \pmod{p} $$ 가우스의 아이디어는 거듭제곱을 $(-1)$ 을 세는 문제로 바꿨지만 우리는 그조차도 셀 생각이 없고 일단은 $|N|$ 으로 두고 넘어갈 것이다. 위와 같은 방식으로 $$ M : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , 1 \le qx - py \le m \right\} $$ 이라고 두면 $$ \left( {{p} \over {q}} \right) \equiv p^{{q-1} \over {2}} = (-1 )^{|M|} \pmod{q} $$ 여기서 $$ |N| + |M| = | \left\{ (x,y) \ | \ 1 \le x \le n , 1 \le y \le m , -n \le qx - py \le m \right\} | $$ 이므로 $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{|N| + |M|} $$ 가 성립한다. 이제 $N$ 과 같은 원소를 공유하지 않는 집합 $$ S = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , n < py - qx \right\} $$ $M$ 과 같은 원소를 공유하지 않는 집합 $$ T : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , m < qx - py \right\} $$ 을 잡자. $f : S \to T $ 를 $$ f(x,y) = (x ' , y ' ) := (n + 1 - x , m + 1 -y) $$ 로 정의하면 $$ \begin{align*} qx’ - py ' &= q(n + 1 - x) - p (m + 1 - y) \\ =& pn + q - qx - pm - p + py \\ =& (pn - pm ) + (p-q) - (qx - py) \end{align*} $$ 여기서 $$ qn - pm = (2m+1)n - (2n+1)m = n - m \\ q-p = 2m + 1 - (2n+1) = 2(m-n) $$ 이므로 $$ qx’ - py ' = n - m + 2m - 2n - (qx -py) =m-n-(qx - py) $$ 따라서 $qx’ - py ' -m = -(qx - py + n) > 0$ 즉 $qx’ - py ' > m$ 이고 $f$ 는 일대일대응이므로 $|S| = |T|$ 다. 이제까지 정의한 $N , M , S, T$ 는 서로 같은 원소를 공유하지 않으므로 $$ |N| + |M| + |S| + |T| = | \left\{ (x,y) | 1 \le x \le n , 1 \le y \le m \right\}| = nm $$ 이제 다시 $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{|N| + |M|} $$ 을 계산해보자. $|S| = |T|$ 이므로 $$ (-1)^{|S| + |T|} = 1 \\ (-1)^{ |N| + |M| } = (-1)^{ |N| + |M| + |S| + |T| } $$ 여기서 $$ |N| + |M| + |S| + |T| = | \left\{ (x,y) | 1 \le x \le n , 1 \le y \le m \right\}| = nm $$ 이므로 $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{nm} $$ $p = 2n + 1$ 이고 $q = 2m + 1$ 이므로 $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$

■

한편 이차상호 법칙은 야코비 기호를 사용함으로써 다음과 같이 홀수에 대해 일반화될 수 있다.

일반화

서로 다른 두 홀수 $a , b$ 에 대해

• [1]’: $$ \left( {{ b } \over { a }} \right) = \begin{cases} \left( {{ a } \over { b }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ a } \over { b }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} $$
• [2]’: $$ \left( {{ a } \over { b }} \right) \left( {{ b } \over { a }} \right) = (-1)^{ { {a-1} \over {2} }{ {b-1} \over {2} } } $$