📂整数論

ルジャンドル記号の乗法的性質の証明

定義

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) $$

■