前回｢その3｣には､原始根の存在と巡回群､それに剰余類群(剰余系)について､様々なコメントが届きましたが､完成度が高いので､そのまま順に纏めます。
原始根の存在と巡回群を使って説明すれば､まず”1のn乗根”とは(幾何学的に言えば)､単位円をn等分する点であり､(代数方程式で言えば)､円周等分方程式:xⁿ=1を満たすn個の解の事となる。
一方で､”1の原始n乗根”とは､それらn個の解(数)のうち､n乗して初めて1となる複素数の事で､自明の実数解である1は除外される。
例えば､1の原始3乗根はω=e^(2πi/3)又はω²=e^(4πi/3)であり､ω,ω²,ω³(=1)は全て3乗根となる。そこで､1の原始n乗根の個数は､オイラーのφ関数φ(n)で与えられ､n個存在する1のn乗根のうちφ(n)個が原始n乗根となる。
また､これら複素数は位数nの巡回群を形成するから､原始根は巡回群の特別な生成元とも言える。一方､群の言葉を使えば､法pの剰余類群Z/pZの原始根とはp−1乗して初めて1になるZ/pZの元の事となるが､原始根が存在する事とその乗法群(Z/pZ)ˣが巡回群になる事は同値であり､原始根とはその巡回群の生成元である事が判る。
つまり､(Z/pZ)ˣの元の個数はφ(p)=p−1あから､原始根gの存在が判れば､(Z/pZ)ˣ={1,g¹,g²,…,gᵖ⁻²}である事も分かる。
もう一度・・原始根とは・・
例えば､素数pの原始根gはgᵏ(modp)が1,…,p−1の全ての数を生成するが､特にpが素数の時､法pにおける既約剰余類群(Z/pZ)ˣは位数p−1の巡回群になるから､1~p−1までの整数gに対し､g¹,g²,…,gᵖ⁻¹(modp)が1,…,p−1の全ての剰余類を生成する時に､gを原始根と呼ぶ。
因みに､オイラーは素数pを法とした時､{1=g⁰,g¹,g²,⋯,gᵖ⁻¹}が全て異なる数gがφ(p−1)個存在する事を発見し､これを原始根と呼んだ。これは､既約剰余類群(ℤ/pℤ)ˣが位数p−1の巡回群になり､その生成元がφ(p−1)個存在する事を意味する。
但し､オイラーは任意の素数について､この原始根の存在を証明出来なかったが､ガウスはこれを厳密な形で証明し､更には任意の奇素数pの冪を法とする時に原始根が必ず存在し､2の冪が法の時は原始根が存在しない事をも証明しました。
仮に､5を法として2の冪乗を計算すると､2⁰≡1､2¹≡2,2²≡4､2³≡3､2⁴≡1となり､既約剰余類群(ℤ/5ℤ)ˣ={1,2,3,4}は2で生成される巡回群になり､2はmod5の原始根となる。
一方で､2ᶜ≡aである時､aを2を底とする指数と呼び､log₂a=cと書くが､ガウスは｢算術研究｣でInd.a=cと書いた。事実､こうした既約剰余類の計算を指数計算に変換する事で､logᵣ関数の形の離散対数を使って合同式を解く事も出来る。これを”離散対数問題”と呼ぶが､指数計算を使う事で､素数冪を法とする既約剰余類群の直積に分解でき､その群の構造が判れば､全ての法での既約剰余類群の構造が判り､原始根の存在を判断できる。
勿論､これらの判定は一筋縄では行かないし､相当な困難を伴う筈だが､若き日のガウスはそれをやってのけたのだ。
再び､剰余定理を群の言葉で言えば､剰余類群(剰余系)を避けて通れないが､厳密には剰余環となる。例えば､nで割った余り(剰余)rが(r=0,1,2,…,n-1)である様な整数全体Zの集合をZrで表すと､整数はZ₀,Z₁,Z₂,…,Zₙ₋₁のn個の部分集合に分類できるが､これら部分集合をnを法とする剰余類と呼ぶ。
これら各剰余類を0,1,2,…,n-1で代表し､その集合をnZと書き､nを法とする剰余系とも呼ぶ。多くはZ/nZと表記し､法nによる剰余類群と書くが､剰余環とも言える。
例えば､整数全体の集合は整域(ab=0⇒a=0又はb=0)だが､Z/nZは整域になるとは限らず､pを素数とするとZ/pZは整域を満たし､その既約剰余類群(Z/pZ)ˣ={1,2,3,…,p-1}となる。また､pが整数の時､既約という意味で剰余環は群となるが故に､(Z/pZ)ˣを既約剰余類群と呼ぶ。
そこで､群の言葉を使い｢フェルマーの小定理｣を語れば､Z/pZ上(a∈(Z/pZ)ˣ)では”aᵖ⁻¹=1が成立する”となり､非常に簡単になる。
また､オイラーのφ関数で言えば､(Z/nZ)ˣの個数はφ(n)となるが､Z/nZ上ではa^φ(n)=1が成り立ち､即座に｢オイラーの定理｣が言える。
この様に､剰余に関する合同式を群に置き換える事で､非常に簡素になるから､抽象的だが群の概念は重要な存在となる。
原始根と巡回群と剰余類群
確かに､整数と言えば”環”というイメージが強いが､pを素数とすれば既約となり､群として語れるから応用が効く。事実､任意の法mに対し､m=p₁^e₁⋯pₖ^eₖと素数分解すれば､(Z/nZ)ˣ≅(Z/(p₁^e₁)z)ˣ⊗⋯⊗(Z/(p₁^eₖ)z)ˣと､素数冪を法とする既約剰余類群の直積に分解され､全ての法の既約剰余類群の構造が判る。
そこで､素数冪を法とする既約剰余類群の構造ですが､(1)法p,p:素数の時､(Z/pZ)ˣ≅<r>,rᵖ⁻¹≡1(modp)､(2)法pᵉ,p:奇素数でe>1の時､(Z/pᵉZ)ˣ≅<r>,r^{pᵉ⁻¹(pｰ1)}≡1(modpᵉ)､(3)法2²=4の時､(Z/2²Z)ˣ≅<−1>,(−1)²≡1(mod4)､(4)法2ᵉ,e>2の時､(Z/2ᵉZ)ˣ≅<−1>×<5>,(−1)²≡5^2ᵉ⁻²≡1(mod2ᵉ)となる。
この時､(1),(2),(3)の場合は巡回群となり､(4)の場合だけ2個の巡回群の直積になる。特にpが奇素数の時は､法pも法pᵉも1つの元だけで生成される巡回群<r>となり､その既約剰余類群の生成元rを原始根と呼ぶ。
一方､1個の元aで生成される巡回群G={aᵏ|k∈Z}で言えば､加法群(有理整数Z)からGへの写像をG:k→aᵏと定めると､加法群から乗法群への全射準同型になる。この写像は離散指数と呼ばれ､位数がnの時､この逆写像をaを底とする”離散対数”と呼び､準同型定理により､全ての巡回群は加法群のZかZ/nZとなる。
ここで､巡回群の性質で言えば､位数nが有限の時､群Gの元aの位数がnとすると､mとnの最大公約数:d=(m,n)とした時のaᵐの位数はn/dとなるが､位数nの巡回群の生成元の個数はφ(n)に等しく､｢オイラーの定理｣から”∑φ(d)=n､d|n”が言え､(Z/nZ)ˣの個数はφ(n)となる事も言える。
また､こうした巡回群Gの重要な性質の1つに､”xᵈ=1を満たす元は高々d個しかない”事があるが､これから奇素数pを法とした既約剰余類群(Z/pZ)ˣは位数p−1の巡回群である事が示され､原始根の存在証明に至る。
最後に､pのべき乗pᵉを法とした既約剰余類群(Z/pᵉZ)ˣは位数pᵉ⁻¹(p－1)の巡回群になる事から､(Z/pZ)ˣの原始根をrとすると､rの位数はpᵉ⁻¹(p－1)となり､rが(Z/pZ)ˣの原始根である事が示せる。
この様に､奇素数pを法とする原始根の存在が保証され､”xⁿ≡a(modp)がd個の解をもつ⇔d=(n,p-1)の時､a⁽ᵖ⁻¹⁾ᐟᵈ≡1(modp)を満たす”との｢冪剰余の判定定理｣を(既述した)離散対数を使って導く事が可能になる。
こうして､原始根の存在の必要十分条件にまで到達させる群論の威力もまた凄まじものがある。
一方で群論では､群の要素の総数を位数(order)と呼ぶが､個数と位数で混乱する人も多いだろうが､実は私もその1人だ(笑)。
例えば､群Gの位数とは群Gを集合と見た時の元の個数､つまり濃度を指すが､元gの位数とは何回掛け合わせて単位元eに戻るのか､つまり､gⁿ=eとなる最小の自然数nの事で､巡回群の位数と一致する。
事実､mod10の加法群:Z/10Z={0,1,2,…,9}の位数は10となる。これは､元1∈Z/10Zの位数は1を10回足すと単位元0に戻るので10となり､元2∈Z/10Zの位数は2を5回足すと0に戻るので5となるからだ。
そこで､群の位数と元の位数の主な性質に､①元g∈Gの位数が1である為の必要十分条件はgが単位元eである事と､②群Gの位数をn<∞とすると､各元g∈Gの位数はnの約数となる事の2つがある。前者は明らかだが､後者は有名な｢ラグランジュの定理｣を使う。
例えば､位数15の群は位数4の部分群を持ち得ないが､4は15の約数ではないから明らかで､素数位数の群Gが巡回群な事も､元e≠g∈Gの位数は素数の約数で､その素数自身となり､G=⟨g⟩=”gの巡回群”となる。事実､この定理は｢フェルマーの小定理｣や｢オイラーの定理｣にもよく使われるから､知っていて損はない。
確かに､位数を単なる個数ではなく濃度とみなす所にコツがあるが､群の構成要素がダブっても濃度は同じで､これは”群Gの位数が有限⇒元g∈Gの位数も有限”であるという重要な性質を示唆する。
これは､群Gの位数は有限で”部屋割り論法”により､g,g²,g³,⋯∈Gの中に同じものが存在するから､gᵐ=gⁿ(但し､m<n)とすると､両辺にg⁻ᵐをかけてe=gⁿ⁻ᵐを得て､元gの位数はn−m以下で有限となる(証明終)。
一方､aⁿ≡1(modp)となる最小の自然数を法pにおけるaの位数(濃度)と呼ぶが､p=7,a=2の時は2⁰≡1,2¹≡2,2²≡4,2³≡1,2⁴≡2,2⁵≡4,2⁶≡1となり､2ᵖ≡(1,2,4)で2の位数は3となる。同様に､a=3の時は2ᵖ≡(1,2,3,4,5,6)で､3の位数は6となる。ここで､位数がp−1になる数をpの原始根と呼ぶが､a=3はp=7の原始根になっている。
原始根を広く浅く理解する為に・・
以上､少し専門的になりすぎて､ついていけない人もいるだろうが､原始根自体はそこまで厄介で抽象的な問題でもない。
事実､｢フェルマーの小定理｣や｢オイラーの定理｣を理解する為に､a,a²,a³,⋯という等比数列を法nの世界で観察するが､例えば､a=2で固定し､法nの値を変えて観察する。
2≡2(mod3)､2≡1(mod3)
2≡2(mod5)､2²≡4､2³≡3､2⁴≡1(mod5)
2≡2(mod11)､2²≡4､2³≡8､2⁴≡5､2⁵≡10､2⁶≡9､2⁷≡7､2⁸≡3､2⁹≡6､2¹⁰≡1(mod11)
と､n=3,5,11の奇素数の時だけ特殊な現象が見られる。事実､n=5の時はmod5=(1,2,3,4)と0~5までの5つの数字の中から0を除く4個で､mod11=(1,2,3,4,5,6,7,8,9,10)も11の数字から0を除く10個となる。但し､同じ奇素数でもn=7の時は1~7の7つの数の中の1,2,4しか登場しない。
だが､n=7の時にa=3とすれば､3≡3,3²≡2,3³≡6,3⁴≡4,3⁵≡5,3⁶≡1(mod7)で､0を除く(1,2,3,4,5,6)の6個が登場する。
つまり､mod7では3が特殊な働きをして､この様な数を原始根と言い､”3は法7での原始根”と呼ぶ。
そこで､原始根を広く理解するには”位数”が重要で､｢その3｣でも言ったが､”aⁿ≡1(modp)となる最小の自然数nを法pにおけるaの位数”と呼ぶ。
例えば､mod7で言えば､｢フェルマーの小定理｣”a⁶≡1(modp)”が成立するが､6は最小の自然数ではなく､2³≡1(mod7)より､mod7における2の位数は6ではなく3となる。
一方､法n=3,5,11にて､1が登場するタイミングは各々2,4,10となり､全てが各々の位数となる。つまり､3,5,11の位数はp−1となる事が判る。これは､”法p(p:奇素数)におけるaの位数がp−1に等しい時､aを法pにおける原始根と呼ぶ”との原始根の定義を満たす。
つまり､(上で観察した様に)原始根はa,a²,a³⋯を奇素数pを法として計算すると､1,2,3,⋯,p−1が登場するという性質を持つ事も判る。
こうした原始根の存在を証明するには､位数だけでなく用意周到な準備が必要になるが､群論を使えば非常に簡素になる。だが､抽象的で高度な道具が必要となり､｢その3｣ではオイラーのφ関数を用いた初等的な証明を長々と説明しました。
この証明で核となるのは､原始根をxᵐ≡1(modp)の解として捉える事で､mod5の例で言えば､合同式:2≡2(mod5),2²≡4,2³≡3,2⁴≡1と､方程式:x⁴≡1(mod5)を見比べ､考えてみる。
まず､2≡2(mod5)では､2⁴≡1(mod5)からx=2がx⁴≡1(mod5)の解となる事は明らかで､以下同様にして､x=2,2²,2³,2⁴が全てx⁴≡1(mod5)の解になる事が判る。
つまり､原始根の存在証明の為には､法pの合同式における高次方程式xᵐ≡1(modp)と､その解の個数についての法則が必要となるが､｢その3｣でも書いた"次数dの整係数多項式f(x)の係数の少なくとも1つがpの約数の時､f(x)≡0(modp)の整数解はd個以下である”という[定理A]に至る。
前回｢その3｣では､[定理A]を含む4つの定理の詳細を省いたが､少しだけ補足する。
まずは[定理A]だが､(i)d=1の時､f(x)=a₁x+a₀より､a₁x+a₀≡0(modp)の解について, f(x)はmodpで1次式である必要があり､係数a₁はpの倍数ではない。故に､a₁とpは互いに素となり､modpにてa₁には逆元が存在し､1次合同式:a₁x+a₀≡1(modp)は必ず解を1つもつ。(ii)d=kで､[定理A]が成立すると仮定し､d=k+1でも定理Aが成立を示す。
仮定よりmodpにおけるk次の方程式の解の個数はk個以下となるが､ここで､k+1次方程式f(x)にてf(x)≡0(modp)を考える。
まず､f(x)≡0(modp)に解が存在しない時､解の個数は0でk+1個以下となり､定理Aは成立。次に､f(x)≡0(modp)に解が存在する時は解をx=aとおくと､因数定理よりf(x)はx−aで割り切れ､f(x)=(x−a)g(x)と表せる。
ここで､g(x)はk次の整係数多項式で､仮定よりg(x)≡0(modp)の解はk個以下となる。よって､f(x)≡0(modp)の解はk+1個以下となり､d=k+1でも定理Aは成立(証明終)。
[定理B]の”aⁿ≡1(modp)を満たすnは必ずmの倍数となる”事は､n=mq+r⇒余りrが発生すると仮定し､指数法則と余りの定義から背理法を使えば､容易に示せる。
[定理C]の”a,a²,a³,⋯,aᵐはどの2つをとってもpを法として合同ではない”事は､aʲ≡aⁱ(modp)､0≦i<j<mと仮定し､背理法により矛盾を示すが､aはpと互いに素であり､aⁱもpと互いに素となり､aʲ≡aⁱ(modp)の両辺をaiで割る事ができる。故に､a⁽ʲ⁻ⁱ⁾≡1(modp)となるが､0≦i<j<mからj−i<mとなり､これはmが法pにおけるaの位数となる事に矛盾(証明終)。
最後に[定理D]だが､nの約数d₁(=1),d₂,…,dₖ(=n)にて､φ(d₁)+φ(d₂)+…+φ(n)=nが成立する｢オイラーの和法則｣に基づくもので､敢えて証明は省きます。
以上､｢その3｣と｢その4｣の2話に渡り､”原始根”をテーマに話を進めましたが､初等整数論の起点となった｢フェルマーの小定理｣と共に重要なテーマです。
次回は､平方剰余の相互法則をp時間時計を使って説明したいと思います。
