📂整数論

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

定義

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$の乗算を見ているようで、実際にそれがルジャンドル記号の核心的なアイデアである。

証明

パート 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である。

---

パート 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}$である。

合同式での乗法逆元：素数$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である。

---

パート 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$も同様にちょうど半分がQR、ちょうど半分がNRであろう。

パート 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という結論に到達するしかない。

パート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}$$

---

ケース 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) $$

---

ケース 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) $$

■