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

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

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

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

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

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

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

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

手順を 4 つに固定する

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

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

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

反転が一度も起きない例

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

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

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

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

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

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

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

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

平方根そのものを求める

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

参考文献