ガウスの平方剰余の相互法則

平方剰余の相互法則について述べたいと思います。

●割り算の余りの概念の拡張・合同式

小学校では、１４を４でわると　商が３で余り２になります。
１４＝４×３＋２
となります。これは余りを０から３（＝４－１）の中から選んでいるので
このように一意的にかけるのですが、その制約をはずせば
１４＝４×４－２
とも表示できます。これは余りがー２と解釈できます。

火曜日は月曜日の１日後ですが、６日前とも解釈できるのと同じことです。

さて、ここから本題に入ります＾＾

m を自然数として a,bを整数とします。

aとbがmを法として合同であるとは
a-bがmで割り切れることと定義します。

いいかえればa-b=mtとなる整数tが存在することとします。

このことを a≡b (mod m)と書くことにします。

通常の＝のように≡も移項したり、両辺に同じ数をかけたりできる
ことに注意してください。

例　a≡b (mod m) ならば　a+c≡b+c (mod m)

何故なら
(a+c)-(b+c)=a-b=mt

と書けるからです。

xを未知数として

x-3 ≡0 (mod m)

のように合同式による方程式を、合同方程式といいます。

この解はもちろん x≡3 (mod m)

です。

＊＊＊

●ルジャンドルの記号

pを奇素数としてaを整数とします。

x^2≡a (mod p)となる解が存在するかしないかという問題を考えます。

（合同式の枠組みで平方根があるかないかという大切な問題です。）

解が存在するとき,(a|p)=1
解が存在しないとき,(a|p)=-1

と書くことにします。
（本当はたてがきなのですが、テキストでは横にせざるを得ませんでした。これはルジャンドルの記号といいます。）

例えば,(-1|5)=1

です。これは

x^2≡-1 (mod 5)の解が存在するということを主張しているわけですが
実際xに２を代入すれば
x^2=4≡-1 (mod 5) で解が存在します。

一方　(-1|3)=-1

です。x^2≡-1 (mod 3)に解がないことを示さなくてはなりません。

x=0,1,2 を代入してどれも≡-1 (mod 3)にならないことを示せば十分です。

（たとえばx=3で解をもったらどうするのか、という疑問が湧くかも知れませんが、
それはx=0の場合に帰着されます。
(x+3)^2=x^2+6x+9≡x^2 (mod 3)に注意していただけたらわかると思います。）

x=0 なら　x^2≡0 (mod 3)
x=1 なら　x^2≡1≡-2 (mod 3)
x=2 なら　x^2≡4≡1 (mod 3)

ですから解がないことがわかりました。

この違いは5が4でわって1余る素数であることに対して、
3が4で割って3余る素数であることに起因しています。

＊＊＊

平方剰余の相互法則とは
与えられた奇素数pと整数aに対して

(a|p)＝±1

を決定するアルゴリズムです。

＊＊＊

●ルジャンドルの記号の性質

pを奇素数としてa,bを整数とします。このとき

(ab|p)=(a|p)(b|p) ---(1)

が成り立ちます。これを証明するにはFermatの小定理というものが必要なのですが、
いまはそのことには触れません。まず、先に証明ぬきでできるだけ早く
平方剰余の相互法則にたどりつくという方針だからです。

a≡b (mod p)ならば
(a|p)=(b|p) ---(2)

が成り立ちます。これは簡単に証明できて

(a|p)=1

⇔　x^2≡a (mod p)に整数解 xがある

(a≡b (mod p)に注意すると）

⇔x^2≡b (mod p)に整数解xがある

⇔(b|p)=1

となるからです。

この２つのルジャンドル記号の性質を組み合わせると次のようなことができます。

例　(6|11)=(2|11)(3|11)

のように6を素因数分解すれば、左の部分をより小さいものに還元できます。
これが式(1)の使い方です。

式(2)の使い方は例えば

(107|7)=(2|7)

のように左側が大きい数のときにそれを7で割ってその余りに置き換えていいので
小さい数に還元できるということです。

このように(a|p)を求めたいときに、なるべく小さい数に還元していくという方針をとります。

＊＊＊

●平方剰余の相互法則

いよいよ真打登場です。

p,qを異なる２つの奇素数とします。

定理（平方剰余の相互法則）

(p|q)(q|p)=(-1)^{(p-1/2)・(q-1/2)} ---(1)

(-1|p)=(-1)^(p-1/2) ---(2)

(2|p)=(-1)^(p^2-1/8) ---(3)

(1)を平方剰余の相互法則、(2)を第一補充法則、(3)を第二補充法則といいます。

まずこれらを日本語に変換します。
(1)から説明します。

(q|p)のpとqを入れ替えたらどうなるかという問題を扱っています。

(p-1/2)が偶数　⇔　pが4で割って1余る素数
(p-1/2)が奇数　⇔　pが4で割って3余る素数

であることに注意すると(1)は次のように主張しています。

(p|q)のpとqを入れ替えるときは、もしp,qのどちらか一つでも4で割って１余る素数であるならば
(q|p)=(p|q)と、同符号になる。
pとqが両方とも4で割って3余るときに限り
(q|p)=-(p|q)と反対符号になる

次に(2)の説明をします。
これは

x^2≡-1 (mod p)が解をもつ
⇔pは4で割って1余る素数である

ということを主張しています。

最後に(3)はまず、

(p^2-1/8)が偶数　⇔　pは8でわって1または-1余る素数である
(p^2-1/8)が奇数　⇔　pは8でわって5または-5余る素数である

ということに注意してください。

{(8n±1)^2-1}/8 = 8n^2±2n
{(8n±5)^2-1}/8 = 8n^2±10n+3

からすぐにわかります。

(2|p)=1 ⇔　pは8で割って±1 余る。
(2|p)=-1 ⇔　pは8で割って±5余る

ということになります。

この(1)(2)(3)と素因数分解を組み合わせるとあらゆるルジャンドル記号の計算が可能になります。

＊＊＊

●平方剰余の相互法則の応用

x^2≡17 (mod 23)が解を持つかどうか調べましょう。

(17|23)を計算すればよいわけです。

まず17と23を入れ替えることを考えます。17が4で割って1余る素数なので

(17|23)=(23|17)

=(6|17) （23≡6 (mod 17)を用いました。）

=(2|17)(3|17) (6=2×3　という素因数分解を使用)

=(+1)(3|17) ((2|17)に第二補充法則を使用。17は8で割って1余る。)

=(3|17)

=(17|3) （平方剰余の相互法則を使用。17は4で割って1余る。）

=(2|3) （17を3で割ると2余る。）

=-1 (第二補充法則を使用。3は8で割って3余る。）

結論　x^2≡17 (mod 23) に解はありません。

問題　x^2≡365 (mod 1847) に解があるかどうか調べよ。

もし、お暇があればやってみてください＾＾

以上です。