The Legendre Symbol

モジュール詳細：ルジャンドル記号

小学校で分数に苦手意識を持っていた皆さん、これを扱わなかったことに感謝しましょう。

各ディスプレーには、1から999の自然数が一つ表示されている。
上のディスプレーの数字は下のディスプレーの数字より小さくなる。
下のディスプレーの数字は三桁の素数になる。
このモジュールを解除するには、qとmをそれぞれ上と下のディスプレーの数字とする。qがmを法とする平方剰余である場合、「R」と書かれたボタンを押す。そうではない場合、「N」と書かれたボタンを押す。
間違ったボタンを押すとミスが記録され、ディスプレー上の数字が変更される。

pを法として平方数と合同である整数qを、pを法とする平方剰余と呼ぶ。つまり、qが平方剰余であるとは、qに対し以下の条件を満たす整数xが存在することを意味する：x² ≡ q (mod p).平方剰余ではない数を平方非剰余と呼ぶ。

例えば、平方数を10で割った余りは0, 1, 4, 5, 6, 9のいずれかになる。したがって、10で割った余りがこれらのうちのいずれかになる数(余りそのものの数も含む)は10を法とする平方剰余である。それ以外の数は平方非剰余である。

特に、奇素数(奇数の素数)pを法とする場合、平方剰余であるかどうかはルジャンドル記号を用いて以下のように示すことができる。

(qp) = {+1-10qがpを法とする平方剰余であるがpの倍数ではないqがpを法とする平方非剰余であるqがpの倍数である

(上記の定義におけるaの「倍数」は負の数やゼロを含む。例えば、14, 49, 0, -21 はすべて7の倍数である)

三番目の条件はこのモジュールでは決して適用されない。これは、「ルジャンドル記号」モジュールでは常に0 < q < pとなるためである。三番目の条件は数学的に完全な式とするために列挙しているだけである。

ルジャンドル記号には興味深い性質がいくつかある。以下はその一部である。

a ≡ b (mod p)とは、pを法としてaとbが合同、つまり、aをpで割った余りがbをpで割った余りと等しいことを意味する。

周期性. pを奇素数とする。 a ≡ b (mod p)の場合：

(ap) = (bp)
相乗性. pを奇素数とする。整数a, bに対し、

(abp) = (ap)(bp)

これは三つ以上の整数に対して拡張することもでき、帰納法によって簡単に証明できる。
平方剰余の相互法則. pとqを異なる奇素数とする。

(pq)(qp) = (-1)^p-12·q-12 = {+1-1p ≡ 1 (mod 4) または q ≡ 1 (mod 4)p ≡ q ≡ 3 (mod 4)

二つの異なる奇数のルジャンドル記号は±1のどちらかしか取らない(一方の素数はもう一方の素数の倍数になることはない)かつ±1の倍数は±1で割り切れるため、この性質は以下のように書き直すことができる。

p ≡ 1 (mod 4) または q ≡ 1 (mod 4)の場合、(pq) = (qp). それ以外は、(pq) = -(qp).
平方剰余の相互法則補足 1. pを奇素数とする。

(-1p) = (-1)^p-12 = {+1-1p ≡ 1 (mod 4)p ≡ 3 (mod 4)
平方剰余の相互法則補足 2. pを奇素数とする。

(2p) = (-1)^p²-18 = {+1-1p ≡ 1 または 7 (mod 8)p ≡ 3 または 5 (mod 8)

前のページの性質を繰り返し適用することで、あるルジャンドル記号の値を、より小さい法における別のルジャンドル記号で示すことができる。

最終的に、法が非常に小さくなると、ルジャンドル記号の値は、平方数を小さい順にいくつか列挙してそれらの剰余を手動で確認する(以下の表を参照)ことで求められる。また、ルジャンドル記号の「分子」が平方数であることを求められれば、定義からそのルジャンドル記号に+1を割り当てることでも求められる。

例えば、14が41を法として平方非剰余であることを示す。上記5つのルールのいずれかを使用して生成された新たな項は、それに応じた注釈が記載されている。

(1441) = (241)(741)(ルール2) = (-1)^41²-18(ルール5)·(417)(ルール3) = (-1)²¹⁰·(-17)(ルール1) = 1·(-1)^7-12(ルール4) = (-1)³ = -1

ルジャンドル記号の値が-1となったため、14は41を法として平方非剰余であることが分かる。

最終的な答えに辿り着くまでのルールの適用方法は複数パターンがあり、より速く効率的な方法もある可能性があるが、常に答えは同じになる。様々なアルゴリズムを試してみて、最適な方法を見つけてみてほしい。

pを法とする平方剰余(pは奇素数)で割った余りを手動で列挙する際、pを法とする平方剰余は[1からp-1までの整数の個数のちょうど半分]個存在し、残りは平方非剰余になることを覚えておくとよいかもしれない(この命題の証明は読者への演習とする)。

以下は、様々な小さい素数について平方剰余を列挙した表である。