📂정수론

르장드르 기호의 곱셈적 성질 증명

정의

QR과 NR은 각각 이차잉여와 비이차잉여를 의미한다. 르장드르 기호^{legendre Symbol}는 $p$ 보다 작은 자연수 $a$ 에 대해 $$\left( { a \over p } \right) = \begin{cases} 1 & a \text{: QR} \\ -1 & a \text{: NR} \end{cases}$$ 과 같이 정의된다. 정수론에서 $\displaystyle \left( {{x} \over {y}} \right)$ 는 분수가 아니라 르장드르 기호^{legendre Symbol}라 하며, 소수가 아닌 자연수에 대해 일반화하면 표기는 똑같이 쓰되 야코비 기호^{jacobi Symbol}라 한다.

정리 ¹

$2$ 보다 큰 소수 $p$ 에 대해 $$\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$$

설명

예를 들어 $p=7$ 에 대해 $1,2,4$ 는 QR이고 $3,5,6$ 은 NR이므로 $$\left( { 1 \over 7 } \right) = \left( { 2 \over 7 } \right) = \left( { 4 \over 7 } \right) = 1$$ 이고 $$\left( { 3 \over 7 } \right) = \left( { 5 \over 7 } \right) = \left( { 6 \over 7 } \right) = -1$$ 이다. 이 기호는 이차잉여에 대한 연산을 매우 편리하게 해주는 곱셈적 성질을 가지고 있다. 곱셈적 성질이란 $f(ab) = f(a)f(b)$와 같이 함수 안팎에서 곱셈을 유지하는 성질을 말한다. 큰 숫자는 그대로 계산할 필요 없이 작은 숫자로 소인수분해해서 계산할 수 있다는 뜻이다.

증명에 앞서 팩트부터 이야기를 하자면 QR과 NR은 다음의 성질을 가진다.

• QR x QR = QR
• QR x NR = NR
• NR x NR = QR

위에서 든 $p=7$ 의 예시를 보며 이 계산이 사실인지 한번 직접 확인해보도록 하자.마치 $1$과 $-1$ 의 곱셈을 보는 것 같고, 실제로 그것이 르장드르 기호의 핵심 아이디어다.

증명

Part 1. QR x QR = QR

$\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$에서 $\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right)$, $\displaystyle \left( { b \over p } \right) = 1$ 인 경우다. $q_{1} = a$ 과 $q_{2} = b$ 가 QR이라고 생각하면, $q_{1} \equiv {m_{1}}^2 \pmod{p}$ 와 $q_{2} \equiv {m_{2}}^2 \pmod{p}$ 를 만족시키는 ${m_{1}}$과 ${m_{2}}$가 존재한다. 따라서 $q_{3} = q_{1} q_{2}$ 라고 하면 $$q_{3} \equiv q_{1} q_{2} \equiv {m_{1}}^2 {m_{2}}^2 \equiv (m_{1} m_{2})^2 \pmod{p}$$ 즉, $q_{3}$ 는 QR이다.

---

Part 2. QR x NR = NR

$\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$ 에서 $\displaystyle \left( { ab \over p } \right) = -1$ 이고, $\displaystyle \left( { a \over p } \right)$ 와 $\displaystyle \left( { b \over p } \right)$ 중 하나가 $1$, 나머지 하나가 $-1$ 일 경우다.

$q = a$ 가 QR, $n = b$ 가 NR이라고 하면 $q \equiv m^2 \pmod{p}$ 을 만족시키는 $m$ 이 존재한다. 둘의 곱인 $r=qn$ 을 QR이라고 가정하자.

그러면 $r \equiv k^2 \pmod{p}$ 을 만족시키는 $k$가 존재해서 $$qn \equiv r \pmod{p}$$ 이므로 $(m)^2 n \equiv (k)^2 \pmod{p}$ 이다.

합동식에서 곱셈에 대한 역원: 정수환 $\mathbb{Z}_{p}$는 $p$ 가 소수면 정수체다. 다시 말해, $\gcd(p,a) = 1$ 면 방정식 $a x \equiv 1 \pmod{p}$ 는 $0<x<p$에서 단 하나의 해를 가진다.

양변에 $(m^{-1})^2$ 을 곱하면 $$n \equiv (m^{-1}k)^2 \pmod{p}$$ 이나, $n$은 NR이므로 이러한 합동식을 만족시키는 $m^{-1} k$가 존재할 수 없다. 이는 모순이므로 $r=qn$은 NR이다.

---

Part 3. NR x NR = QR

$\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$ 에서 $\displaystyle \left( { ab \over p } \right) = 1$ 이고 $\displaystyle \left( { a \over p } \right) = \left( { b \over p } \right) = -1$ 인 경우다.

$n = a$ 을 NR이라고 하자. 소수 $p$ 에 대해, $1,2, \cdots (p-1)$ 중 정확히 절반은 QR, 정확히 절반은 NR이다. 페르마의 소정리를 증명할때와 비슷하게 $n, 2n, \cdots (p-1)n$ 을 생각해보면 마찬가지로 $n, 2n, \cdots (p-1)n$ 역시 정확히 절반은 QR, 정확히 절반은 NR일 것이다.

우리는 Part 2에서 QR x NR = NR 임을 보였으므로 $n$과 어떤 QR의 곱은 NR일 것이다. 그 말인 즉슨 $1,2, \cdots (p-1)$ 에서 QR이었다면 $n, 2n, \cdots (p-1)n$에선 NR이라는 뜻이다. 이런 NR들의 개수는 정확하게 $\displaystyle {{p-1} \over 2}$이고 QR도 정확하게 $\displaystyle {{p-1} \over 2}$ 개가 되어야한다. 이것이 가능하려면 NR x NR = QR 라는 결론을 내릴 수밖에 없다.

위의 Part 1~3을 요약해서 르장드르 심볼로 나타내면 다음과 같다. $$\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$$

■

한편 르장드르 기호의 곱셈적 성질과 가우스의 이차상호 법칙을 사용하면 다음의 따름정리를 얻는다. 이는 속칭 ‘분모’에 대해서도 르장드르 기호의 곱셈적 성질이 통한다는 것을 의미한다.

따름정리

$2$ 보다 큰 소수 $a$ 에 대해 $$\left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right)$$

따름정리의 증명

가우스의 이차 상호 법칙: $$\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}$$

---

Case 1. $a \equiv 1 \pmod{4} \lor pq \equiv 1 \pmod{4}$

$$\left( {{ a } \over { pq }} \right) = \left( {{ pq } \over { a }} \right) = \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right)$$ $a \equiv 1 \pmod{4}$ 이므로 $$\left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right)$$

---

Case 2. $a \equiv 3 \pmod{4} \land pq \equiv 3 \pmod{4}$

$$\left( {{ a } \over { pq }} \right) = - \left( {{ pq } \over { a }} \right) = - \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right)$$ $pq \equiv 3 \pmod{4}$ 이므로 $p \equiv \pm 1 \equiv - q \pmod{4}$ 이고, $$- \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right)$$

---

위의 케이스들을 정리하면 어떤 경우든 다음이 성립한다. $$\left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right)$$

■