ガウスの平方剰余の相互法則はどこが美しいのか

Tweet

Pocket

ガウスの黄金定理としても知られる平方剰余の相互法則。何十個もの証明がなされているそうですが、この定理がどのように美しいのかという説明は難しいです。

実際に僕が高校生ぐらいの時に初めて見た時も、なかなか綺麗な性質があるなとは感じたものの、例えばオイラーの公式を見たときのような衝撃はなかったように思います。

しかしガウスが黄金定理と呼ぶにはそれなりの訳があったのでしょう。改めてこの定理についての証明と説明を読んでいた時に、この定理の美しいところがようやく自分なりに理解できたため、解説記事を書くことにします。

この記事においては、詳しい証明はしません。各自気になるところは自分で調べてください。

基本的なこと

証明はしませんが、記号の意味がわからなければ何もわからないかと思いますので、簡単に説明します。

合同式

「\(\equiv\)」は合同を表します。
\(7 \equiv 2\;(5)\)
これは、7も2も5で割った余りは同じであるという意味です。言い換えると、7と2の差は5で割り切れるということを指しています。

一般的には\(a \equiv b\;(p)\)という使い方をして、\(a-b\)が\(p\)で割り切れるということを表しています。
このように、整数論では余りの世界で議論することがしばしばあります。

そして整数や実数や複素数の世界で「この方程式を解くことはできるのか？」ということが重要な疑問であったように剰余（余り）の世界においても方程式が解くことができるのかどうかという問題は大きな問題です。

例えば

\(ax \equiv b\;(m)\)

という合同式は\(a\)と\(x\)の最大公約数が\(b\)を割り切った時のみ解を持ち、解の個数はその最大公約数の数と等しいことが確かめられます。

ルジャンドル記号

自然な流れで

\(x^2 \equiv a\;(p)\)

という合同式を考えてみましょう。この式は、\(a\)と\(p\)の組み合わせによって解を持ったり持たなかったりします。この式が解を持つのかどうかに関する定理が平方剰余の相互法則です。

「\( \left( \frac{ a }{ p } \right ) \)」はルジャンドル記号と言います。ここで\(p\)は素数です。

\(x^2 \equiv a\;(p)\) が解を持つ時に \( \left( \frac{ a }{ p } \right ) = 1\) と定義され、
\(x^2 \equiv a\;(p)\) が解を持たない時に \( \left( \frac{ a }{ p } \right ) = -1\) と定義され、
\(p\)が\(a\)を割り切る時に \( \left( \frac{ a }{ p } \right ) = 0\) と定義されます。

1. \( \left( \frac{ a }{ p } \right ) \equiv a^{(p-1)/2} \;(p) \)
2. \( \left( \frac{ ab }{ p } \right ) = \left( \frac{ a }{ p } \right ) \left( \frac{ b }{ p } \right ) \)
3. \(a \equiv b\;(p)\) ならば \( \left( \frac{ a }{ p } \right ) = \left( \frac{ b }{ p } \right ) \)

といった性質を持っています。

周辺の定理について

先ほど紹介した式を見てください。

\( \left( \frac{ a }{ p } \right ) \equiv a^{(p-1)/2} \;(p) \)

これです。この式は結構強力です。今は \(x^2 \equiv a\;(p)\) という合同式を考えていました。この式に例えば具体的に数を当てはめていったとしましょう。例えば \(x^2 \equiv 3\;(7)\) という式が解を持つか調べてみましょう。

\( \left( \frac{ 3 }{ 7 } \right ) \equiv 3^{(7-1)/2} \equiv -1\;(p) \) となるため、これは解を持ちません。

このように、具体的な式が与えられた場合には、解を持つか持たないかの判定がすぐにできてしまうのです。

もしもあなたが7月7日生まれで、7という数字を深く愛しているとしたら、あなたは次にこう思うかもしれません。

「\(x^2 \equiv a\;(7)\) という式が解を持つような\(a\)を全て見つけ出したい。」
つまり、\( \left( \frac{ a }{ p } \right )=1 \) となるような\(a\)を全て見つけ出したいのです。
\(1\)から\(6\)までを同様に計算すると、\(a=1,2,4\)の時に解を持つことがわかります。\(8\)以上の\(a\)に関しては、\(1\)から\(6\)のどれかと合同であるので、\(1\)から\(6\)までを計算しさえすれば十分なのです。

考えなければならない\(a\)が有限なので、
「ある \(a\) に対して \(x^2 \equiv a\;(p)\) という式が解を持つような\(a\)を全て見つけ出したい。」
という欲求は満たされるのです。

次に\(7\)という数字が好きなあなたはこう思うかもしれません。
「\(x^2 \equiv 7\;(p)\) という式が解を持つような素数\(p\)を全て見つけ出したい。」
何を隠そう、これが平方剰余の相互法則の動機なのです。

この議論の難しいところは考えなければならない素数\(p\)が有限ではなく、無限に広がっていることです。先ほどの
\( \left( \frac{ a }{ p } \right ) \equiv a^{(p-1)/2} \;(p) \)
という性質では、一つ一つの値を求めることはできますが、\(p\)が平方剰余である（解を持つ）ための隠された条件を見つけ出すことはできないのです。

そして、それは平方剰余の相互法則によって天地がひっくり返るような方法で達成されます。

その前に、「ある \(a\) に対して \(x^2 \equiv a\;(p)\) という式が解を持つような素数\(p\)を全て見つけ出したい。」という問題の特別な場合について紹介しましょう。

\(a = -1\) の時と \(a = 2\) の時に関する法則で第1補充法則と第2補充法則と呼ばれているものです。

1. \( \left( \frac{ -1 }{ p } \right ) = (-1)^{(p-1)/2} \)
2. \( \left( \frac{ 2 }{ p } \right ) = (-1)^{(p^2-1)/8} \)

第1補充法則は \( \left( \frac{ a }{ p } \right ) \equiv a^{(p-1)/2} \;(p) \) という先ほどの式に\(a = -1\) を代入すると出てきます。
ここでポイントは \(p=4k+1\) と表される時は平方剰余であり、\(p=4k+3\) と表される時は平方非剰余である、と言い換えることができるということです。

また第2補充法則は少し導出が複雑ですが、こちらも同様に言い換えることができます。 \(p=8k+1\) 又は \(p=8k+7\) と表される時は平方剰余であり、\(p=8k+3\) 又は \(p=8k+5\) と表される時は平方非剰余であるのです。

一見無限にあると思われた素数\(p\)も、\(4\)や\(8\)による剰余を考えて有限通りの場合分けをして特徴付けることができるようになるのです。

そして、とうとう\(-1\)や\(2\)だけではなく、一般の値\(a\)について\(a\)が平方剰余となるような素数を探し、その素数を剰余によって特徴付けましょう。

平方剰余の相互法則

平方剰余の相互法則とは以下の等式のことで、\(p\)と\(q\)が奇数の素数であるときに成り立ちます。

右辺は、\(p\)か\(q\)のどちらかが \(p=4k+1\) と表される時は1となり、どちらも\(p=4k+3\)と表される時は\(-1\)となります。

これだけを見ても何が凄いのかあまりわからないことでしょう。
この定理の素晴らしさを伝えるために、しばしば \( \left( \frac{ 79 }{ 101 } \right ) \) などの具体的な値を実際に求めてみよう！といった例題が出されます。実際に求めてみると、分母と分子を逆転させることにより、手計算によってある程度簡単に計算できるようになります。
この手法は、実際に使ってみるとそこそこ感動するのですが、実際にこれぐらいの計算ならば何度も出てきた
\( \left( \frac{ a }{ p } \right ) \equiv a^{(p-1)/2} \;(p) \)
という式でもコンピューターを使えば一瞬で答えが出ますし、この定理の本当の感動ポイントはここではないと思うのです。

先ほどの問題を思い出してください。私たちは「ある \(a\) に対して \(x^2 \equiv a\;(p)\) という式が解を持つような素数\(p\)を全て見つけ出したい。」という問題を考えていました。
このことに対して、平方剰余の相互法則から以下のことが言えます。

いきなり読んでも少し理解しづらいかもしれません。
\(q=3\)の時についてまず考えてみましょう。これは\(4k+3\)と表される素数の場合に当てはまります。
この時、\(b\) として取りうる12(\(3 \times 4\))以下の値は、\(1,5,7,11\)であり、これらは2乗すると全て12による剰余の世界では1に等しくなります。よって、3が平方剰余となるような素数は12で割った余りが\( \pm 1\) であるような素数であると特徴付けられます。
次に\(q=5\)の時について考えてみましょう。これは\(4k+1\)と表される素数の場合に当てはまります。\( \left( \frac{ r }{ 5 } \right ) = 1 \) となるような\(r\)は1と4なので、5が平方剰余となるような素数は5で割った余りが\(1\) か \(4\) であるような素数であると特徴付けられます。

以上の例で見たように、\(q\)が平方剰余となるような\(p\)の条件を探すという行為を、\(q\)や\(4q\)の剰余の世界において\(p\)の条件を探すという風にひっくり返すことができるというのが平方剰余の相互法則の強みなのです。

つまり、無限に続く素数の中を条件に合う素数が見つかるように果てしなく探索するのではなく、有限な剰余の世界に持っていって特徴づけることができるという定理なのです。

いつの間にかひっくり返されていた剰余に僕はこの定理の美しさを見たのでした。

最後に「\(x^2 \equiv 7\;(p)\) という式が解を持つような素数\(p\)を全て見つけ出したい。」という問題に答えを与えておきましょう。\(q=3\)の時と同じ方法を使います。

これは\(4k+3\)と表される素数の場合に当てはまります。
この時、\(b\) として取りうる28(\(7 \times 4\))以下の値は、\(1,3,5,9,11,13\)です。\(b^2 = (-b)^2\)なので、15以上については考えなくても良いのです。
これらは2乗すると\(1,9,-3,3,-1,1\)となります。よって、7が平方剰余となるような素数は28で割った余りが\( \pm 1, \pm 3, \pm 9\) であるような素数であると特徴付けられます。

具体的にあげると、\(3,19,29,31,37,47,53,…\)のような整数の列を作ることができます。

参考図書

以上の内容は以下の本を参考に書きました。気になる人はぜひ買ってみてください。

Tweet

Pocket