ルジャンドル記号を互除法のように畳む - 相互法則と補充法則の実演

$x^{2} \equiv 30 (mod 101)$ に解があるかを判定してください。 $101$ は素数です。

総当たりなら $50$ 回の $2$ 乗で済みますが、記号を畳めば $4$ 行で終わります。 $30 = 2 \cdot 3 \cdot 5$ と分けます。

$(\frac{30}{101}) = (\frac{2}{101}) (\frac{3}{101}) (\frac{5}{101})$

$2$ は補充法則です。 $101 \equiv 5 (mod 8)$ なので $(\frac{2}{101}) = - 1$ 。

$3$ には相互法則を当てます。 $101 \equiv 1 (mod 4)$ なので符号は反転せず、 $(\frac{3}{101}) = (\frac{101}{3})$ 。 $101 \equiv 2 (mod 3)$ で、 $3$ を法とする平方数は $0$ と $1$ だけなので $- 1$ です。

$5$ も同じで、 $(\frac{5}{101}) = (\frac{101}{5}) = (\frac{1}{5}) = + 1$ 。

掛け合わせて $(- 1) (- 1) (+ 1) = + 1$ 。解があります。実際 $3 8^{2} = 1444 = 101 \cdot 14 + 30$ で、 $x = 38$ と $x = 63$ が解です。

手順を 4 つに固定する

どの問題も同じ流れで進みます。

真数を素因数分解し、記号を掛け算に分ける。

- 1

と

2

は補充法則で処理する。

奇素数どうしは相互法則で上下を入れ替える。

入れ替えたら余りに置き換え、

1

に落ちるまでくり返す。

$4$ 番目で数が小さくなるので、ユークリッドの互除法と同じ速さで終わります^[2]。

符号が反転するのは、上下がどちらも $4$ で割って $3$ 余るときだけ。片方が $1$ 余れば、そのまま入れ替えられます。

反転が一度も起きない例

$(\frac{105}{1009})$ を求めてください。 $1009$ は素数です。

$1009 \equiv 1 (mod 4)$ なので、どの奇素数と組んでも符号は反転しません。ここが効きます。

$105 = 3 \cdot 5 \cdot 7$ と分け、 $3$ つとも上下を入れ替えます。

$(\frac{3}{1009}) = (\frac{1009}{3}) = (\frac{1}{3}) = + 1$ 。 $1009 = 3 \cdot 336 + 1$ だからです。

$(\frac{5}{1009}) = (\frac{1009}{5}) = (\frac{4}{5}) = + 1$ 。 $4 = 2^{2}$ なので平方数です。

$(\frac{7}{1009}) = (\frac{1009}{7}) = (\frac{1}{7}) = + 1$ 。 $1009 = 7 \cdot 144 + 1$ 。

答えは $+ 1$ 。解は $x = 431$ と $x = 578$ です。

$1009$ が $4$ で割って $1$ 余る、という一点だけで計算がここまで軽くなります。

平方根そのものを求める

$p \equiv 3 (mod 4)$ のときは、解があると分かれば式で書けます。 $x = a^{(p + 1) /4}$ が平方根になる。

$x^{2} = a^{(p + 1) /2} = a \cdot a^{(p - 1) /2} \equiv a \cdot (\frac{a}{p}) = a$ となるためです。指数 $\frac{p + 1}{4}$ が整数になるのが $p \equiv 3 (mod 4)$ の効き目。

$p = 103$ 、 $a = 2$ で試します。 $103 \equiv 7 (mod 8)$ なので $(\frac{2}{103}) = + 1$ 、解はあります。

$x = 2^{26} mod 103$ を計算すると $38$ 。実際 $3 8^{2} = 1444 = 103 \cdot 14 + 2$ です。

$p \equiv 1 (mod 4)$ では、この近道がありません。判定は同じ手順でできても、根を求めるには別の手続きが要ります。

ヤコビ記号で因数分解を省く

真数が大きいと素因数分解が重くなります。分母を奇数の合成数まで広げたヤコビ記号を使うと、分解せずに同じ規則で畳めます。

$(\frac{219}{383})$ をヤコビ記号として計算すると $+ 1$ が出ます。 $383$ が素数なので、この場合はルジャンドル記号としても $+ 1$ です。

ただし落とし穴があります。分母が合成数のとき、ヤコビ記号が $+ 1$ でも平方剰余とは限りません。

$(\frac{2}{15}) = (\frac{2}{3}) (\frac{2}{5}) = (- 1) (- 1) = + 1$ ですが、 $15$ を法とする平方数は $0, 1, 4, 6, 9, 10$ の $6$ 個で $2$ は入りません。

ヤコビ記号が $- 1$ なら平方剰余でないと言い切れます。

$+ 1$ のときだけ結論が出ない。素数を法とするときは、この区別が消える。

二次体の分解則に読み替える

$(\frac{30}{101}) = + 1$ という結果は、 $Q (30)$ で $101$ が完全分解することを意味します^[3]。

$30 \equiv 2 (mod 4)$ なので判別式は $120$ 。奇素数 $p$ が $∤ 120$ なら、 $(\frac{120}{p}) = (\frac{30}{p})$ が分解の判定です^[2]。

$(\frac{d _{K}}{p}) = + 1$	$(p) = p p^{'}$ と完全分解する
$(\frac{d _{K}}{p}) = - 1$	$(p)$ は素イデアルのまま
$p ∣ d_{K}$	$(p) = p^{2}$ と分岐する

相互法則を使うと、この条件を $p$ を法とする話から判別式を法とする話に翻訳できます^[2]。分解のパターンが $p mod ∣ d_{K} ∣$ だけで決まる、という形になります。

$19$ 世紀末には、この翻訳を高次へ広げたいという動機が円分体の研究を押し進めました^[1]。

$(\frac{7}{19})$ はいくつですか。

$+ 1$
$- 1$
$0$

__RESULT__

$7$ と $19$ はどちらも $4$ で割って $3$ 余るので、相互法則で符号が反転します。 $(\frac{7}{19}) = - (\frac{19}{7}) = - (\frac{5}{7})$ 。 $7$ を法とする平方数は $1, 2, 4$ で $5$ が入らないので $(\frac{5}{7}) = - 1$ 、よって答えは $+ 1$ です。

分解する、補充法則を当てる、入れ替える、余りをとる。この $4$ 手をくり返すだけで、 $3$ 桁でも $4$ 桁でも数行で答えが出ます。

参考文献

Keith Conrad, *History of class field theory*, University of Connecticut

B Edixhoven, L Moret-Bailly, *Théorie algébrique des nombres*, Université de Rennes 1

Quadratic field - Encyclopedia of Mathematics

$\left(\frac{30}{101}\right)$ は $2, 3, 5$ に分け、$101 \equiv 5 \pmod 8$ から $-1$、$101 \equiv 2 \pmod 3$ から $-1$、$101 \equiv 1 \pmod 5$ から $+1$ で、答えは $+1$。実際 $38^2 = 101 \cdot 14 + 30$ です。$\left(\frac{105}{1009}\right)$ では $1009 \equiv 1 \pmod 4$ なので反転が一度も起きない。$p \equiv 3 \pmod 4$ なら $x = a^{(p+1)/4}$ で平方根そのものが書け、$p = 103$、$a = 2$ で $x = 38$。ヤコビ記号が $+1$ でも $\left(\frac{2}{15}\right)$ のように平方剰余とは限らない話まで。