前回｢その2｣では､合同式と剰余計算の美しい世界を簡単な例を挙げて説明しました。
ガウスは自著｢アリトメチカ研究｣でオイラーが取り上げた｢フェルマーの小定理｣を絶賛しますが､それに続く｢原始根の存在定理｣では円周等分方程式(巡回方程式)の解の構造を明らかにし､高次の冪剰余法則に繋げ､アーベル方程式へと繫ります。
事実､ガウスが8通りもの証明を与えた平方剰余の相互法則は､初等的整数論の原型となり､その後､代数的整数論から代数関数論へと大きく飛躍します。
「その1｣でも触れた様に､オイラーの算術はガウスの初等的整数論を発掘し､アーベルは､ガウスから代数方程式論を､オイラーからは楕円関数論を新たに創出しました。従って､代数方程式論は数論と結びつき､ガウスは複素整数域にて4次剰余相互法則を､クロネッカーはアーベル方程式の実態を模索し､類体論という神秘の花を咲かせます。
平方剰余とは､元々はオイラーが最初に発見し､論理的に証明した美しき等式(合同式)でもあり､例えば､”pが4m+1の形の素数の時､x²+1はpで割り切れる”という平方数の理論で､x²≡−1(modp)というシンプルな合同式で与えられる。
この様に､オイラーは数学にひたすら美を求めたが､ガウスは厳密さを求めた。
つまり､剰余(mod)という美しい概念から円周等分方程式の既約性(代数的可解性)を厳密に論じた若きガウスの瞳には､オイラーとその平方剰余論の先を明確に捉えていた。事実､ガウスはオイラーでも成し得なかった｢原始根の存在定理｣の証明に成功する。
因みに､ガウスが絶賛し､オイラーが自身の定理(｢オイラーの規準｣)に繋げた｢フェルマーの小定理｣は､一般に”aᵖ⁻¹≡1(modp)”と書くが､aᵖ≡a(modp)と変形すれば､”aをp乗すると必ずaに戻る”との素数p時間時計となる。
また､”平方剰余と可解性”の視点で言えば､合同式x²≡a(modp)が解xを持てば､(a/p)=1となり､平方剰余となるが､(a/p)=−1の時には解xを持たず平方非剰余となる。但し､(a/p)を”ルジャンドル記号”と呼ぶが､”オイラーの規準”では､a⁽ᵖ⁻¹⁾ᐟ²≡1(modp)なら可解であり､−1であれば不可解(平方非剰余)と判定できるから､この2つは同義と言える。
更に､異なる奇素数p,q間での｢平方剰余の相互法則｣では､より複雑な合同方程式の可解性を判定できるが､ガウスにより初めて証明された。この相互法則を言い換えれば､p時間時計とq時間時計の相互関係とも言える。
一方で､ガウスは円周等分方程式の考察から､xⁿ≡A(modp)の形をしたn次合同方程式の代数的可解性を論じ､そこから2つの補充法則を発見。”アリトメチカの真理を発見した”と興奮して､平方剰余の基本定理と名付けた。
これに関しては､次回｢その4｣で詳しく説明するが､平方剰余の相互法則は､数論の美しさと深さを示し､RSA暗号や楕円曲線暗号などの分野でも大きな役割を果たす事となる。
｢フェルマーの小定理｣と｢原始根｣の存在
話をガウスが創り出した初等整数論のボス的存在である”原始根”に戻しますが､その由来は｢フェルマーの小定理｣にあり､オイラーも熟知してはいたが､厳密に証明したのは”原始根を見つける方法の大部分は試行錯誤に支えられていた”と指摘したガウスであった。
事実､｢フェルマーの小定理｣によく似た｢原始根の存在｣は､一見自明に思えるもののその証明は困難だった。確かに､オイラーのφ関数を使ったオイラーによる証明は不完全で､帰納的観察によるものが多かったからで､ガウスはそれを厳密に証明したかった。
因みに”原始根”とは､ある素数pを法とする乗算において､べき乗すると1からp−1までの全ての数を1度ずつ作り出せる数(解)の事で､”aᵏ≡1(modp)なる最小のkがp−1”となり､”その数aをpの原始根”と呼ぶが､オイラーのφ関数で言えば”φ(p)=p−1の位数を持つ元”となる。一方､p−1が位数となる元はpの原始根となり､素数pには原始根が必ず存在する。
ここで､原始根を理解するには”位数”という概念を知る事が非常に重要で､”aⁿ≡1(modp)となる最小の自然数nを法pにおけるaの位数”と呼ぶが､原始根をrとすると､r,r²,⋯ ,rᵖ⁻¹をpで割った余りは全て異なり､1〜p−1までを一巡する。
例えば､p=7の時､3¹≡3(mod7)､3²≡9≡2(mod7)､3³≡27≡6(mod7)､3⁴≡81≡4(mod7)､3⁵≡243≡5(mod7)､3⁶≡729≡1(mod7)と､3のべき乗を続けると､3,2,6,4,5,1と1〜6までの全ての数が生成される。従って､3は7の原始根となり､その元はp−1=6が位数となる事が判る。
但し､”modpにおけるaの位数をnとすると､aᵐ≡1(modp)⇒mはnの倍数”という位数の性質だが､その証明は”a,a²,⋯, aⁿ⁻¹はpで割った余りが1でない”と”aⁿはpで割った余りが1になる”との位数の2つの条件を使い､mをnで割った余りが0になる事を示す。
そこで､mをnで割った商Q､余りRとおき､[条件2]から､1≡aᵐ=a^(nQ+R)=(aⁿ)^Qaᴿ≡1^Qaᴿ=aᴿ(modp)となり､aᴿ≡1(modp)を得るが､余りR(0≤R<n)≠0と仮定すると[条件1]に矛盾。よって､R=0が示せた(証明終)。
そこで､原始根と位数を理解する為の応用例として､素数pに対し”(p−1)!≡−1(modp)”を満たす｢ウィルソンの定理｣があるが､p=2pの時は明らかでpが奇素数の時を証明する。
まず､素数pの原始根rをとると､rの位数はp−1で､r,r²,⋯ ,rᵖ⁻¹をpで割った余りは全て異なり､1〜p−1までを一巡し､r⋅r²⋯rᵖ⁻¹≡1⋅2⋯p−1(modp)となる。よって､rᵐ≡(p−1)!(modp)―(※)を得る(但し､m=1+2+⋯+(p−1)=p(p−1)/2)。
一方､｢小定理｣よりr²ᵐ=rᵖ⁽ᵖ⁻¹⁾≡1(modp)なので､(rᵐ−1)(rᵐ+1)はpの倍数となるが､rᵐ≡1(modp)と仮定すると､位数の性質よりmはp−1の倍数である。故に､m/(p−1)=p/2は整数の筈だが､これはpが奇数に矛盾し､rᵐ≡−1(modp)となり､(※)と合わせて｢ウィルソンの定理｣が証明できた。
確かに､1,2,3,...,p−1の中で自分自身が逆元になるのは1とp−1だけで､他の数は異なる数とペアを組み､その積が1になり､故に､(p−1)!≡1×(p−1)≡−1(modp)が言える。
この様に､｢フェルマーの小定理｣に始まり､それを一般化した｢オイラー関数φの定理｣から｢ウィルソンの定理｣に向かう流れは見事であり､以降ガウスの｢平方剰余｣やルジャンドル記号による｢相互法則｣へと繫がる。
一方､原始根の概念に依拠して”円周等分方程式は代数的に可解である”との命題を確立したガウスは､原始根の中に”諸根の相互関係”を明確な形で見出した。オイラーも原始根の概念は認識してたが､ガウスの様な明確な意図は見られなかった。
そこで､”aᵖ⁻¹≡1(modp)”なる｢小定理｣を振り返ると､aの冪a,a²,a³…を作る時､p−1乗に達する前に早々と≡1(modp)となる可能性があるが､仮にそうならない時､即ち”aはp−1乗して初めて≡1(modp)になる”なら､そのaこそが原始根となる。
例えば､a=7は素数p=19で原始根ではないが､a≡7(mod19)､a²≡11(mod19)､a³≡1(mod19)となり､途中で≡1(mod19)となる。同様にして､a=2は素数p=19で原始根である事が判る。つまり､素数pの原始根rをとり､rのp−1個の冪1,r,⋯ ,rᵖ⁻²を作り､これら各々にてpに関する最小剰余を作ると､原始根の性質から1,2,3,…,p−1と一致する事が判る。他方で､円周等分方程式:xᵖ⁻¹+xᵖ⁻²+…x+1の根(1のp乗根)はe^(2πki/p)､k=1,2,…,p-1で表されるが､原始根rʲを使えば､全体としてe^(rʲ2πki/p)､j=1,2,…,p-2という形に表示される。
そこで､原始根の1つをg=e^(2πi/p)とすると､根の全体はg,g^r,g^r²,…,g^rᵖ⁻²と簡潔に表され､ここでガウスは関数φ(g)=g^rを導入し､根の全体はg,φ(g),φ(φ(g)),…,φ(φ(…(φ(g))))…(p−2回の合成)との表示を受け入れた。ガウスはこの事実を持って”円周等分方程式は巡回方程式だ”と明言する。
この様に､円周等分方程式の諸根が特異な相関関係で結ばれてる事が原始根の性質から明らかになり､この事実を梯子にガウスは円周等分方程式の可解性を示した。
この様に､原始根という数の個性から代数方程式の世界に分け入るガウスの創意とアイデアには脱帽しかないが､このガウスの代数方程式論を正しく汲んだのが､若き日のアーベルであったのだ。
ガウスによる｢原始根の存在定理｣の証明
再び､｢原始根の存在定理｣に戻り､”法pにおけるaの位数がp−1である時にaを法pにおける原始根”と呼ぶ事は前にも言ったが､簡潔に言えば､”aをp−1乗して初めて1と合同になる数”の事である。だが､｢小定理｣では”aをp−1乗すると1と合同になる”事を言ってるだけで､原始根のそれとは異なる。
そこで､｢原始根の存在証明｣に入るが､ここでは､xⁿ≡1(modp)の方程式(n次合同式)の解を原始根とみなし､数学的帰納法を使って証明する。実際ガウスはオイラーの関数φ(n)を模したϕ(n)使った事に留意し､話を進めます。
まず最初に､”p−1の約数n(p−1はnの倍数)にて､xⁿ≡1(modp)の解がn個ある”事を示すが､n乗して1と合同になる数を押さえ､最後にn乗して初めて1と合同になる数を数え上げ､存在証明を終えるという2段階の流れになる。
即ち､初めにp−1の約数nにて､n乗して1と合同になる数がn個ある事を証明し､次に､n乗して初めて1と合同になる数の個数を数え上げ､その個数がφ(n)個となる事を証明する。
以下､｢原始根の存在定理をわかり易く丁寧に｣を参考に大まかに纏めます。
そこで､まずは｢小定理｣により､1<x≦p-1なる全てのxに対し､xᵖ⁻¹≡1(modp)が成立し､p−1=nsからxᵖ⁻¹−1=xⁿˢ−1=(xⁿ)ˢ−1を得る。
この時､Xˢ−1=(X−1)(Xˢ⁻¹+Xˢ⁻²+⋯+X+1)が成立し､この式にX=xⁿを代入すると､(xⁿ)ˢ−1={(xⁿ)−1}{(xⁿ)ˢ⁻¹+(xⁿ)ˢ⁻²+⋯+(xⁿ)+1}=xᵖ⁻¹−1―①が成立。
ここで､xᵖ⁻¹≡1(modp)の解の個数は｢小定理｣によりp−1個あり､f(x)=(xⁿ)−1､g(x)=(xⁿ)ˢ⁻¹+(xⁿ)ˢ⁻²+⋯+(xⁿ)+1とおくと､f(x)はn次式より､f(x)≡0(modp)の解はn個以下となる(∵[定理A])。同様に､g(x)はn(s−1)次式より､g(x)≡1(modp)の解はn(s−1)個以下となる。故に､①式の右辺にて､f(x)g(x)≡0(modp)の解の個数は､n+n(s−1)=ns=p−1個以下と分かる。
また､(左辺)≡0(modp)の解の個数と(右辺)≡0(modp)の解の個数は一致すべきで､f(x)g(x)≡0(modp)の解の個数は丁度p−1個となり､”xⁿ−1≡(modp)の解の個数も丁度n個”となる(証明終)。但し､これを[定理E]とする。
ここから後半に入るが､p−1の約数nにて､n乗して1と合同になる数xがn個ある事から､x(1≦x≦p−1)が丁度φ(n)個存在する事をp−1の約数においての数学的帰納法により証明を行う。
(i)p−1の最小の約数1の時､x¹≡1(modp)の解はx=1のみで､1乗して初めて1と合同になる数は1個のみ。故に､φ(1)=1となり､p−1の最小の約数1について成立。
(ii)nより小さいp−1の約数について成り立つ。即ち､nより小さいp−1の約数dにて､d乗して初めて1と合同になる数x(1≦x≦p−1)の個数がφ(d)個と仮定する時､n乗して初めて1と合同になる数x(1≦x≦p−1)が丁度φ(n)個な事を示す。
そこで､n乗して初めて1と合同になる数x(1≦x≦p−1)の個数を仮にψ(n)とおき､ψ(n)=φ(n)を示せればいい。事実､ガウスは(前述の様に)オイラーの関数φ(n)を模したϕ(n)使った。
まず､nの約数を小さい順に､d₁(=1),d₂,⋯,dₖ(=n)とすると､帰納法の仮定より､di乗して初めて1と合同になる数はφ(di)個となる(i=1,2,⋯,k−1)。
そこで､自然数a(1≦a≦p−1)に対し､aⁿ≡1(modp)が成り立つとすると､この時､nより小さい数mに対し､aをm乗して初めて1と合同になるなら､[定理B]よりmはnの約数であるべきだ。
逆に､nの約数mにてaをm乗して初めて1と合同になるとすると､aⁿ=(aᵐ)ⁿᐟᵐ≡1(modp)が成立し､これらを踏まえ､nの約数diとa(1≦a≦p−1)にて､aをdi乗して初めて1と合同となるなら､aⁿ≡1(modp)が成立する―②。
いま､n乗して1になる数全体の集合をAnとし､di乗して初めて1と合同になる数全体の集合をBdiとすると､②よりAn=Bd₁∪Bd₂∪⋯∪Bdₖ⋯③が成立すべきである。そこで､③式の両辺の集合の要素の数を数え上げる。
まず､右辺については[定理E]より､xⁿ≡1(modp)を満たす解の個数はn個である④。また左辺にては､帰納法の仮定よりdi乗して初めて1と合同になる数はφ(di)個(i=1,2,⋯,k−1)だったので､Bdiの要素の個数はφ(di)個となる⑤。但し､dₖ=nより仮定で使えるのはdₖ₋₁までで､n乗して初めて1と合同になる数の個数はψ(n)と置いた事に留意する。
いま､④⑤より､n=φ(d₁)+φ(d₂)+⋯+φ(dₖ₋₁)+ψ(n)―⑥を得る。ここで[定理D]より､n=φ(d₁)+φ(d₂)+⋯+φ(dₖ₋₁)+φ(n)―⑦となるから､⑥⑦よりψ(n)=ϕ(n)が成立し､数学的帰納法より､原始根の個数がφ(n)個となる事が示された(証明終)。
因みに､下準備として以下の4つの定理を用意したが､合同式における位数の概念を理解できれば､最後の[定理E]だけで十分だとは思うが､念の為に4つの定義を載せておく。
[定理A]"次数dの整係数多項式f(x)の係数の少なくとも1つがpの約数の時､f(x)≡0(modp)の整数解はd個以下である”の証明はdにおける数学的帰納法を使うが､”f(x)がx−aで割り切れる⇔f(a)=0⇔x=aがf(x)=0の解となる”との[因数定理]を用い､f(x)≡0(modp)の解が存在する時としない時に分けて証明する。
[定理B]”mを法pにおけるaの位数とする時､aⁿ≡1(modp)を満たすnは必ずmの倍数となる"の証明はnが倍数でない(n=mq+r⇒余りrが発生する)と仮定し､指数法則と余りの定義から背理法を使い､矛盾を示す。
[定理C]”上の同条件の時､a,a²,a³,⋯,aᵐはどの2つをとってもpを法として合同ではない”は､これは否定の証明であり､合同である時の矛盾を示す。
[定理D]”nの約数をd₁(=1),d₂,⋯,dₖ(=n)とすると､φ(d₁)+ϕ(d₂)+⋯+ϕ(n)=nが成り立つ”が､これはオイラーφ関数の和の性質から導ける。
但し､これら4つの定理は｢原始根の存在証明｣の厳密さを要請する為に書いておく。
最後に
後半は少し複雑になったが､既述の様にガウスは数論的関数ϕ(d)を導入したが､pは奇素数でdはp−1の約数とすると､”pより小さい数でそのd次の冪が1と合同な最低次の冪な性質を持つ数の個数”をϕ(d)で表せる。
そこで､ガウスはϕ(d)をオイラー関数φ(d)と比較し､等しい事を示した。特に､d=p−1の場合､ϕ(p−1)=φ(p−1)であり､明らかに右辺≠0から､原始根の存在が証明でき､同時に原始根の数も計算可能になる。
更にガウスは”原始根の存在を主張する定理は､如何に慎重さが必要であるかの著しい範例を与えてくれる”と語ったが､原始根の存在証明は(自明だとして)オイラーを除いては誰も証明を与えようとはしなかった。
更に”オイラー氏が提出した証明には2つの欠陥がある。1つには､xⁿ≡1がn個の相異なる根を持つ事を暗に仮定してるが､([定理A]で示される様な)n個より多くの根を持ち得ない事以外は何も証明していない。もう1つは､単に帰納的観察を通じて導出されたものに過ぎない”と断罪している。
事実､当り前に見えても数論の世界においては､証明が難しい現象はしばし出会う。が故に､”数学は美しいだけじゃなく厳密であるべきだ”とオイラーに釘を刺したガウスは､未だ数学の王に相応しい存在ではある。
本来なら､原始根と位数の関係を｢フェルマーの小定理｣や｢オイラーのφ定理｣を理解する際にやる様に､a,a²,a³,⋯という等比数列を奇素数aで固定し､modpの値を変えながら(ガウスがやった様に)1つ1つ観察する必要がある。勿論､原始根の存在証明は今では様々な方法があり､群論を用いた証明が最も簡素だが､オイラーのφ関数を用いた証明が最も複雑だが理解はしやすい。
ガウス版”青春の夢”とも言える原始根の存在証明を終えた所で､今日は終りにします。
次回｢その4｣では､平方剰余の相互法則をp時間時計を例にして説明したいと思います。
