ガウスの平方剰余と相互法則(更新)〜美しきガウスの黄金定理とは？

　｢中国人の剰余定理｣では､1次方程式の剰余定理について述べました。
　少し振り返りますと､1次(不定)方程式のax+by=cが解を持つ為の必要十分条件は､”cがaとbの最大公約数d=(a,b)の倍数”である事でした。
　この時､ax≡c(mod b)､by≡c(mod a)の2つの合同式が成り立ち､前者のax≡c(mod b)はd=1の時､x≡p(mod b)という形の解があり､d>1の時はx≡q(mod c/d)という形の解がある。というものです。
　言い換えれば､ax≡b(mod c)という合同式は､bがaとcの最大公約数の倍数である時に解け､特にaとcが互いに素(最大公約数が1)であれば､bがどんな数であっても解ける事を発見した。

　つまり､昔の中国人(孫氏)も江戸時代の日本人も､剰余(余り=mod)という概念(整数論)を使って､方程式の解が存在するか否かを探っていたんですね。
　以上を定理に直せば､”与えられた2つの整数m,nが互いに素ならば､任意の整数a,bに対し､連立合同方程式x≡a(mod m),x≡b(mod n)を満たす整数xがmnを法として一意的に存在する”となります。
　因みにこの証明は､古代ギリシャ人の”ユークリッド互除法(拡張版)”を用いて解きました。

　この中国の剰余定理は､宣教師により19世紀のヨーロッパにも伝えられ､ガウスの剰余定理と同等のものとされてます。
　ガウスは2次の剰余定理(平方剰余)をも公式化します。
　x²≡a(mod p)が解を持つ時(a,p互いに素)､aはpを法として”平方剰余”と呼び､この合同式の解の判定法を”平方剰余の相互法則”と呼んだ。
　以上､長々と振り返りました。

ガウスの平方剰余とは？

　そこで今日は､ガウスの黄金定理としても知られる”平方剰余の相互法則”について紹介します。
　因みに､以前にも｢ガウス”その4”｣や｢リーマン”2の9”｣その他でも度々触れてますが､今回は少し突っ込んで説明したいと思います。

　ガウスは､あるxに対し､x²−a(整数)がp(素数)で割り切れれば､xは合同式x²≡a(mod p)の解となる事を発見した。　　
　この式に解が存在する時､”aはpの平方剰余”となり､解が存在しないなら”aはpの平方非剰余”となります。
　そこでガウスは､ルジャンドル記号(a/p)を使い､(a/p)=1の時は解を持ち(平方剰余)､(a/p)=−1の時は解を持たない(非平方剰余)と定義します。
　但し､pがaを割り切る(a≡0(mod p))時は(a/p)=0も定義する。しかし､通常は前提としてa,pは互いに素とするから､もしこの仮定を外しa=0とすれば､x²≡0(mod p)はx=0という解を常に持つので､a=0は外し､(a/p)=0も外す時があります。
　またp=2の時､x²≡a(mod 2)はa=1となるから､x²≡1(mod 2)は常に解を持つ事が明らかなので､pを奇素数(3以上の素数)とする事が多いですね。この前提条件はしっかりと理解しましょう(補足)。

　このガウスの”平方剰余”には､大きく3つの性質があります。
　①(a/p)≡(√a)ᵖ⁻¹(mod p)､②(ab/p)=(a/p)(b/p)､③a≡b(mod p)⇒(a/p)=(b/p)。
　特に､①の性質はとても強力です。但し､(a/p)≡a^((p−1)/2)(mod p)とした方がわかり易いですかね。
　因みに､②はルジャンドル記号上での積表示となり､③は(剰余での)合同が等号になる事を示してます。この2つの基本的性質もよく使いますから覚えとく必要があります。
　以下､｢平方剰余の相互法則はどこが美しいのか｣から一部抜粋して説明します。

　ここで､x²≡3(mod 7)という式が解を持つかを調べてみます。そこで①の公式に当てはめると､(3/7)≡(√3)⁷⁻¹(mod 7)≡3³(7)=27(7)=−1より(定義から)解を持たない。
　この様に､具体的な式が与えられた時は､すぐに解の判定が出来ます。
　では､x²≡a(mod 7)という式が解を持つaを全て探し出す時はどうするのか？
　つまり､(a/7)≡a³(mod 7)=1なるaを全て見つけ出す為には､まずa=1~6までを同様に計算すると､a=1,2,4の時に解を持つ事がわかる。
　そこで､aが8より大きい時は､1~6のどれかと合同(7で割った余りが全て1~6)なので､1~6までを計算するだけでいい。
　故に､ある有限なaに対し､”x²≡a(mod p)が解を持つaを全て見つける”事が可能になります。

”平方剰余の相互法則”とは？

　次に､x²≡7(mod p)という式が”解を持つ素数pを全て見つけ出す”時はどうするのか？
　これこそが､”平方剰余の相互法則”が存在する真の理由です。
　そこで､素数pがaの様に有限ではなく､無限である事が､大きな壁になります。
　①の性質では､1つ1つの値を求める事はできるが､pが解を持つ(平方剰余である)為の条件を見つけ出す事はできない。
　そこで､a=−1の時とa=2の時に関する法則で､第1補充法則と第2補充法則と呼ばれてるもので､それぞれ(−1/p)=(−1)^((p−1)/2)､(2/p)=(−1)^((p²−1)/8)で示される2つの法則を使います。
　第1補充法則は､①式の(a/p)≡(√a)ᵖ⁻¹(mod p)にa=−1を代入すると導けます。
　ここで､p=4k+1の時は平方剰余((−1/p)=1)で､p=4k+3の時は平方非剰余((−1/p)=−1)である､と言い換える事が出来ます。
　これは(−1/p)=1の時は(p−1)/2が偶数だから､(p−1)が4の倍数よりp=4k+1。−1の時は(p−1)/2が奇数より､(p−1)が4で割って2余るからp=4k+3(証明終)。
　また､第2補充法則は少し複雑ですが､p=8k+1又はp=8k+7の時は平方剰余((2/p)=1)であり､p=8k+3又はp=8k+5の時は平方非剰余((2/p)=−1)と言い換えれます。
　この様に､無限にある素数pも4や8による剰余を考え､(aが−1や2の)有限通りの場合分けをして特徴付ける事が出来る。

　そこで､一般の値aについてaが平方剰余となる様な素数を探し､その素数を剰余によって特徴付けてみます。
　”平方剰余の相互法則”とは､”p,qが相異なる奇素数の時､(q/p)(p/q)=(−1)^{(p−1)/2}{(q−1)/2}という公式が成立”する事です。
　この時､pかqのどちらかが4k+1の形なら､右辺の(p-1)/2と(q-1)/2のどちらかが偶数より､この積も偶数となり､(q/p)(p/q)=1となる。また､どちらも4k+3の形なら､共に奇数より､(q/p)(p/q)=−1となる。
　ここで､p,qが異なる奇素数より(q/p)=1又は−1となり､(q/p)²=1が使え､(q/p)(p/q)=1又は−1の両辺に(q/p)を掛けると､平方剰余の相互法則は､(p/q)=(q/p)又は−(q/p)と書き換える事が出来る。勿論､符号の条件は上と同じです。
　この書き換えにより､aを素因数分解し、平方剰余の相互法則と第一第二補充法則を用い､ルジャンドル記号を一般のケースでも計算できる。
　例えば､(26/47)の値を求めるには､分母と分子を逆転させ､手計算によってある程度は簡単に計算できる。しかし､これぐらいの計算なら冒頭で述べた平方剰余①の(a/p)≡a^((p−1)/2)(mod p)の公式でも､コンピューターを使えば一瞬で答えが出る。
　故に､｢ガウスの黄金定理｣の本当の美しさはこんなもんじゃない。　

平方剰余の相互法則の真意

　そこで､”平方剰余の相互法則”の公式を使い､x²≡a(mod p)が解xを持つ素数pを全て見つけ出す事にトライしてみます。
　まず､”平方剰余の相互法則”の定義から､
　(ⅰ)素数q=4k+1の時､(q/p)=1である事と､ある(r/q)=1となる様なrに対し､p≡r(mod q) となる事は同値である。
　(ⅱ)素数q=4k+3の時､(q/p)=1である事と､あるqと互いに素な奇数bに対し､p≡±b²(mod 4q)となる事は同値である。

　この2つの定義はとても抽象的に見えますが､簡単な例をとって順に説明するとわかり易い。
　まずq=3を例に取れば､(ⅱ)のqが4k+3で表される素数ですね。この時､bとして取りうる12(3×4)以下の値は(3と互いに素な奇数より)､1,5,7,11であり､これらは2乗すると､全て12による剰余の世界では1に等しい。
　故に(逆から見れば)､3が平方剰余となる様な素数は､12で割った余りが±1である様な素数と特徴付けられる。よって(ⅱ)が成立する。
　これは､1≡b²(mod 4×3)の時､3がpの平方剰余((3/p)=1)とp≡±1(mod 4×3)が同値を示している。
　次にq=5を例に取れば､これは(ⅰ)の4k+1と表される素数ですね。
　(r/5)=1となるr(≤5)は､(r/5)≡r²(mod 5)=1より1と4なので､5が平方剰余となる素数は､5で割った余りが1か4である素数と特徴付けらる。故に(ⅰ)が成り立つ。
　これも､(r/5)=1となるr=1,4に対し､(5/p)=1とp≡r(mod 5)が同値を示してる。

　最後に､”x²≡7(mod p)が解を持つ様な素数pを全て見つけ出し”てみます。
　これも､q=3の時と同じ方法を使う。q=7は(ⅱ)の4k+3と表される素数ですね。
　この時､bが取りうる28(7×4)以下の値は(7と互いに素な奇数より)､1,3,5,9,11,13です。
　但し､28の半分の15以上は2乗すると以下の様に､b²=(−b)²より同じ繰り返しになるので考えなくてもいい。
　これらを2乗すると､28による剰余の世界では､1,9,−3(25),3(81),−1(121),1(169)となる。
　よって､7が平方剰余となる素数は､28で割った余りが±1,±3,±9である素数と特徴付けらます。具体的には､p=3,19,29,31,37,47,53,…の様な素数列ですね。

最後に〜美しきかな”ガウスの黄金定理”

　以上､”おとなぱすた”サンのコラムからでした。追記を加え､ダラダラと長くなりましたが､平方剰余の相互定理をその雰囲気だけでも理解するには､これくらいは最低でも知っておきたいです。
　因みに､(26/47)の値を求める例題の解答はpaulさんのコメントに書かれてあるので､参考にして下さい。ルジャンドル記号の特徴に慣れるには丁度いいですね。

　以上のように､qが平方剰余となるpの条件を探す行為を､qや4qの剰余の世界においてpの条件を探すという風に”ひっくり返す”というトリックが､平方剰余の”相互法則”の強みです。
　つまり､無限に続く素数の中で条件に合う素数を果てしなく探索するではなく､有限な剰余の世界に持っていき､条件を満たす素数を特徴づけるという定理です。
　この”ひっくり返された”平方剰余に､相互定理の美しさがある。　

　次回以降でも書く予定ですが､”整数論の起源と歴史”という観点から眺める場合､ある程度の理解は必要だと思うので､長い紹介になってしまいました。
　確かに､書いてて非常に抽象的で､優しくは説明されてありますが､これこそが整数論の難解さと不可解さでしょうか。
　qが平方剰余となる様な素数pは､qが4k+1と4k+3の時で場合分けして考え､q又は4qの剰余の世界にひっくり返し､pを探り出す。
　つまり､無限の考察を有限の世界で考えたガウスのお見事な”美しき黄金法則”だったんです。

　因みに(次回で述べますが)､ルジャンドルは1785年に､この(剰余定理の)”相互法則”を発表しますが､どうしても証明する事が出来なかった。
　しかし1801年(実際は1796年)に､ルジャンドルよりも25歳も若い24歳のガウスは､ルジャンドルとは異なる視点から厳密な2種類の証明を与えます。
　長くなりすぎたので､今日はここまでです。次回は､この平方剰余の相互法則の起源について述べたいと思います。