原始根と指数(3-補足)

前回は記事の最後に後少しなのでこの記事に追加します。

と書きました。

しかし,色々私事に追われて時間的な間もかなり開きましたし,追加分

を補足の別記事としました。

本記事では,まず,具体的に素数ｐの原始根を求める方法を模索

します。

自然数：ｇが素数ｐの原始根なら,ｄ|(ｐ－1),かつｄ＜(ｐ－1)なる

自然数：ｄに対しては決してｇ^d≡1 (mod p)となることはなく,他方,

ｇ^p-1≡1 (mod p)が成立しています。

また,もしもｋ＜(ｐ－1)なるｋに対してｇ^k≡1 (mod p)が成立するなら

ｇはｐの原始根ではありません。

これらは原始根の定義そのものですが,以下の原始根の探索では

本質的なことなので,ここで改めて強調しておきました。

原始根の導出には,次の補助定理に頼る方法があります。

その他にも方法はあるでしょうがここではこれだけを紹介します。

[補助定理]：(ａ,ｐ)＝1,(ｂ,ｐ)＝1なるａ,ｂについてそれらの法ｐにおける

位数をそれぞれ,ｘ＝ord(ａ), ｙ＝ord(ｂ)とする。このとき,

(ⅰ ) (ｘ,ｙ)＝1なら法ｐでのａｂの位数は,ord(ａｂ)＝ｘｙである。

(ⅱ) (ｘ,ｙ)＝ｄ＞1なら,法ｐにおいて,ord(ｃ)＝[ｘ,ｙ] なるｃで(ｃ,ｐ)

＝1を満たすものが存在する。

(証明)：合同式は全て素数ｐを法としたものなので,以下の証明

では記号：(mod ｐ)を全て省略します。

(ⅰ) ａ^ｘ≡1,ｂ^ｙ≡1より,(ａｂ)^ｘｙ＝(ａ^ｘ)^ｙ(ｂ^ｙ)^ｘ≡1 です。

そして,(ｘ,ｙ)＝1なのでｄ＝ord(ａｂ)とすると,ｄは互いに素なｘとｙの約数

である２つの因数の積に分解できて,ｄ＝ｄ₁ｄ₂；ｄ₁|ｘ,ｄ₂|ｙ,(ｄ₁,ｄ₂)＝1と

表わすことができます。

それ故,ｘ＝ｘ₁ｄ₁,および,ｙ＝ｙ₁ｄ₂と書けば,(ａｂ)^ｄ＝(ａｂ)^ｄ1ｄ2≡1 です。

この両辺をｘ₁乗すると,{(ａｂ)^ｄ1ｄ2}^ｘ1＝ａ^ｘｄ2ｂ^ｘｄ2≡1なので

ｂ^ｘｄ2≡1を得ますが,ｙ＝ord(ｂ)なのでｙ|(ｘｄ₂)です。

ところが,ｙ＝ｙ₁ｄ₂なのでｙ₁|ｘですが,(ｘ,ｙ)＝1よりｙ₁＝1です。

同様に,{(ａｂ)^ｄ1ｄ2}^ｘ2＝ａｙ^ｙｄ1ｂ^ｙｄ1≡1 から ｘ₁＝1 を得ます。

したがって,ｄ＝ord(ａｂ)ｘｙ＝ｘｙです。

(ⅱ)ｘ₀|ｘなら{ａ^(ｘ/ｘ0)}^ｘ0＝ａ^ｘ≡1です。

そこで,{ａ^(ｘ/ｘ0)}^ｋ≡1でｋ＜ｘ₀ならｋ|ｘ₀ですから,

(ｘ/ｘ₀)ｋが整数でａ^{(ｘ/ｘ0)ｋ}≡1,かつ(ｘ/ｘ₀)ｋ≦ｘ

となります。

これは,ｘがａの位数であるという仮定に矛盾するため,

ｘ₀はａ^(ｘ/ｘ0)の位数です。

同様にｙ₀|ｙならｙ₀はｂ^(ｙ/ｙ0)の位数です。

そこで,ｄ＝(ｘ,ｙ)＞1の場合

ｘ'＝ｘ/ｄ,ｙ'＝ｙ/ｄとおくと(ｘ',ｙ')＝1で,かつ,

ｘ'＝ord(ａ^ｄ),ｙ'＝ord(ｂ^ｄ)なので,

今証明したばかりの(ⅰ)によりｘ'ｙ'＝ord(ａ^ｄｂ^ｄ)です。

それ故,ａ^ｄｂ^ｄ＝(ａｂ)^ｄであり(ａｂ)^{ｄｘ’ｙ’}≡1です。

そして,ｘとｙの最小公倍数は明らかに

[ｘ,ｙ]＝ｄｘ'ｙ'です。

そこで,ｃ＝ａ^αｂ^β(α,β∈Ｎ,1≦α≦ｄ,1≦β≦ｄ)なる

形式のｃの中にord(ｃ)＝ｄｘ'ｙ'＝[ｘ,ｙ],を満たすもの

が存在すると予測できます。

例えば,ｃ＝ａ^ｄｂとおけば法ｐでｃ^ｄｘ'ｙ'≡1です。

そして,ｋ≦ｄｘ'ｙ',かつ,ｃ^ｋ＝ａ^ｄｋｂ^k≡1なら,

ｋ|(ｄｘ'ｙ')ですからｄ＝ｄ₁ｄ₂,ｘ'＝ｘ₁ｘ₂ ,

ｙ'＝ｙ₁ｙ₂としてｋ＝ｄ₁ｘ₁ｙ₁と表現されます。

このとき.ｃ^ｋ＝ａ^ｄｋｂ^k≡1はａ^{ｄｄ1ｘ1ｙ1}ｂ^ｄ1ｘ1ｙ1≡1

と書けます。

最後の合同式の両辺をｘ₂乗するとｂ^ｄ1ｘｙ1≡1です。

故に,ｙ＝ord(ｂ)よりｙ≦(ｄ₁ｘｙ₁)であり

ｙ|(ｄ₁ｘｙ₁)です。

そこで,ｙ＝ｄｙ'＝ｄｙ₁ｙ₂ですから(ｄｙ₂)|(ｄ₁ｘ)ですが,

(ｘ,ｙ₂)＝1より,結局,(ｄｙ₂)|ｄ₁,つまり,(ｄ₂ｙ₂)|1を得ます。

したがって,ｄ₂ｙ₂＝1である他なく.自然数の範囲ではｄ₂＝ｙ₂＝1です。

よってｋ＝ｄｘ'ｙ'でありord[ｃ]＝ｄｘ'ｙ'＝[ｘ,ｙ]が得られました。

(証明終わり)

さて,１つだけしか例を与えませんが,下の例は上記の補助定理を

適用した１例です。

[例]：素数がｐ＝191とすると(ａ,191)＝1ならFermatの小定理

により,ａ^p-1＝ａ¹⁹⁰≡1 (mod 191)です。

そして,ａ＝2とすると2¹⁹⁰≡1 (mod 191)であり,それ故,

2⁹⁵≡±1 (mod 191)です。

そして実際には2⁹⁵≡1 (mod 191)となるのでord(2)＝95です。　

(※何故なら, 2⁹⁵＝(2⁵)¹⁹,ですが, 2⁹＝512＝191×2＋130,

2¹⁰＝1024＝191×5＋69から2¹⁹≡69×130＝8970＝191×47－7,

2⁹⁵≡(－7)⁵＝－16807＝－191×88＋1≡1 を得るからです。

2のベキ乗が対象の場合,平方剰余の相互法則などを利用するのは,

むずかしそうなので,泥臭いですが具体的計算をしました。

ｐが素数で(ａ,ｐ)＝1のとき,

Fermatの小定理からａ^p-1≡1 (mod ｐ)ですが,ｐが奇数なら,

(ｐ－1)が偶数なので(ｐ－1)/2は整数です。

そして,{ａ^(p-1)/2}²≡1 (mod ｐ)ですから,奇素数ｐについては

σ(ａ)＝ａ^(p-1)/2≡±1 (mod ｐ)です。

ここで,平方剰余の相互法則などの定理で多用される

Legendreの記号：(ａ/ｐ)＝σ(ａ)＝ａ^(p-1)/2≡±1 (mod ｐ)

を導入すると,

(ａｂ/ｐ)＝(ａ/ｐ)×(ｂ/ｐ)が成立します。

謂わゆる平方剰余の相互法則はｐ,ｑ共に奇素数 なら

(ｐ/ｑ)(ｑ/ｐ)＝(－1)^(p-1)(q-1)/4であり,それ故に,

(ｐ/ｑ)＝(ｑ/ｐ)(－1)^(p-1)(q-1)/4というものです。

一方,(2/ｐ)＝(－1)^{(p^2-1)/8}という法則から,

(2/19)＝(－1)⁴⁵＝－1,(2/5)＝(－1)³＝－1という情報

が得られます。

もしも,上記法則において素数ｐ,ｑのうちｐが偶数の2でも

よければ上記法則から(19/2),(5/2)が得られますから,

95＝9・19,(95/2)＝(19/2)×(5/2) etc.の考察から

2⁹⁵≡1という考察も可能でしょう。

しかし,ｐ＝2は奇数でないので,適用できずこの方法は断念して

スマートじゃない泥臭い計算になりました。※)

一方,ｂ＝7とすれば7¹⁰≡1 (mod 191),ｙ＝ord(7)＝10 です。

(ｘ,ｙ)＝(95,10)＝5＝ｄ＞1,ｘ₁＝ｘ/５＝19,ｙ₁＝ｙ/5＝2,

2⁹⁵＝(2⁵)¹⁹≡1 (mod 191),7¹⁰＝(7⁵)²≡1 (mod 191),

(ｘ₁, ｙ₁)＝(19,2)＝1,[ｘ,ｙ]＝ｘ₁ｙ₁ｄ＝19×2×5＝190

(2⁵×7⁵)³⁸≡1 (mod 191),(19,10)＝1,[ｘ,ｙ]＝ｄｘ₁ｙ₁＝190

(2⁵×7)¹⁹⁰≡1 (mod 191)であり,

2⁵×7＝32×7＝214＝191＋33＝33 (mod 191),

そこで33¹⁹⁰≡1 (mod 191)です。

したがって,ｇ＝33はｐ＝191の１つの原始根です。

最後に一応題名に入れたので,指数という概念を簡単に

紹介します。

例から述べます。

素数ｐをｐ＝7とするとｇ＝3.5はｐの原始根です。

mod7では3≡3,3²≡2,3³≡6,3⁴≡4,3⁵≡5,3⁶≡1,

また 5≡5,5²≡4,5³≡6,5⁴≡2,5⁵≡3,5⁶≡1です。

これを見ると明らかに,ｇ＝3,5共に右辺に1,2,3,4,5,6 が

1回ずつ出現しています。

これについては次の定理があります。

[定理4]:素数ｐの原始根をｇとすると,(Ｚ/ｐＺ)^×はｇを生成元

とする巡回群である。

(証明)：ｇ⁰＝1,ｇ,ｇ²,..,ｇ^p-2,ｇ^p-1≡1 (mod ｐ)です。

1,ｇ,ｇ²,..,ｇ^p-2は全て異なる(ｐ－1)個の元ですから明らかに

{1,ｇ,ｇ²,..,ｇ^p-2}＝{12,..,ｐ－1}＝,(Ｚ/ｐＺ)^×を得ます。

(証明終わり)

そこで,上記例の１つのｇ＝5の例において

5¹≡5,5²≡4,5³≡6,5⁴≡2,5⁵≡3,5⁶≡1 (mod 7)を,

それぞれ,Ind₅5＝1,Ind₅4＝2,Ind₅6＝3,Ind₅2＝2,

Ind₅3＝5,Ind₅1＝6と書くことにします。

これが5に対する指数なのですが,定義は次のようになります。

[定義]：素数ｐの原始根ｇに対してｇ^ｋ≡ａ(mod ｐ)のとき,

Ind_ｇ(ａ)＝ｋと書き,これをｇを底としたａの指数,または

離散対数という。

これは,通常の対数logの合同式版と考えられます。

これについても色々な考察があるようでしたがこれ以上の

進展<にそれほど興味が持てなかったので入院時のノートも

ここで次の論題に移っているため,この論題については

ここで終了します。

無為徒食(畜生(ちくしょう))。。普通の日記

　生活が無為徒食に近づいているようです。

　夢も目標もなければ,ただ単に空腹なら食べ,ノド乾いたら飲み,それプラス排泄に睡眠の繰り返しという生活.。。

　少なくとも衣食が足りているなら家畜には悪いが,家畜同然の生活＝畜生(チクショウ)ですネ。

　イヤ,衣食足りていない民も多勢いて日々飢え死にしたりしてるのだからそれ以上を望むのはゼイタクだと,このブログでは一貫して記述してきていますがそれはヒトの社会的人間という側面です。

　一方では実存的人間の部分もあるわけで,余裕がないならそういう部分は持てないのだから,確かにゼイタクといえばゼイタクには違いなく有閑階層の道楽であって両刃の剣です。

　まあ,素朴な火にしても問題の原発の原子力にしても便利なものとリスクは同居していて全て両刃の剣ですし,個人情報も昔のコトワザ？のように「向こう３軒両隣り」として隣人と思って心配する対象であればそれは善意にとって便利で親切な情報ですし,近代の都会的西洋的イメージで自己のエゴに利用してやろうと思えばリスクです。

　恐らくあらゆるモノゴトは,両刃の剣でしょう。

　※デフレを解消せんとすればインフレを産み,デフレとインフレの振れ幅が増大し歯止めを失ってスーパーインフレとスーパーデフレを導いてついには,カタストロフ(大破局)大恐慌を迎えてパンクするのか？それともデフレ,インフレの振れ幅は次第に減少して弁証法的,自然淘汰的にピンポイントのデフレでもインフレでもない安定点に近づいていくのか？

　人間のエゴに基づく経済活動(下部構造)は如何なる安定性のクリタリオンによって支配されているのでしょうか？。。※

　私的問題としては,今も決して全ての夢を諦めたワケではなく年齢を重ね体力等の衰えや病気によって,いくつかの夢はそれを目指して行動することさえ不可能となって,結果,見られる夢の数は減っていっていますが

　元々,草食系,インドア派傾向の方が強い私は,年老いても,座っていても寝ていてもそれに向かって進めるようなメインの夢がありました。。

　Ｄream(ドリーム)。。Ｄｉｅ　Traume(トロイメ)。。いやトラウマも含めて,人生も後残り少ないのだから現在でも可能な限りのアソビができるうちは快楽主義になってもいいじゃないか？的な側面もあって,

　メインの夢は恐らく最期までに実現不可能と予期されるので,昔より短期的日常的,目標不達成に深刻でなくなり,ストイックで貧乏性的分野のモチベーションこそ失われつつありますが。。

　病気で入院,退院をくり返してガタのきた体と心の今でも,細々と夢に向かおうとする意欲はズッと継続して残っています。

　それに,今では大抵の苦しいことさえ,楽しみのウチです。

　まだ,若い正社員時代にも,。。

「チミの場合,アカデミックというより垢デミック,晴耕雨読というより晴眠雨眠,Walking Dictionary(生き字引き)というよりワーニングプロチョンだね。」とチャカされ,電車に乗って帰宅するまで背中に「バカです。」などの張り紙を下げたまま気付かないなどよく遊ばれて喜んでいたのも懐かしい思い出です。

　マゾであり,,また,イジメや上司の叱責にもシカられてることにさえ気付かないような「朴念仁」でしたかｔら。。今の相変わらずで鈍感なシアワセ者かも。。

　まあ,タマには安い酒でも食らってヨタ話したり,ヘタな歌でもネ。。

　昔。新宿ゴールデン街が地上げで無くなる危機には黒征(クロセイ)デザイン？の１枚100円カンパのＴシャツを買いましたが。。それには「酒を捨てれば夢も死ぬ」とイキな文句書いてました。

　昔なつかし,「造反有理」や「あらゆる犯罪は革命的である。」などの名文句も多々ありましたね。。

　犯罪は社会の矛盾の縮図であって,犯罪者の多くは決して弱者の敵ではなく,寧ろ味方でしょう。実際歴史的にも,かつてのフランス革命など近代の政治革命の発端は監獄での騒乱や暴動という例が多数ありましたね。

　しかし,誰かが組織しないと。。。()オウムや統一教会じゃダメだヨ)

　味方同士で傷つけ合ってどうする？

　くしくも昔のアベの祖父？の岸首相時代の60年安保当時から私も参加した70年安保粉砕運動のデモ活動は当時の警察機動隊によって弾圧を受けましたが,今もまさに小規模ですが国会付近でのシュプレヒコールさえテロ扱いでそのうち弾圧に会いそうで懐古趣味的にはワクワクしますが。。。

　ある意味では,安倍クンが首相になって本来モットモやりたかったことをヤリ始めたんでしょうかね。

　人民大衆は数年に２,３回の選挙での投票行動以外には,政治参加は一切許さないという。。,現在のカタナでもあるペンや言説etcを封じる"刀狩り"のようなものでしょうか。。

　(※内緒ですが私自身はテロもゲリラ活動の一種と概念規定していて強者に対抗する弱者の１つのマヌーバ(戦術)と思っているので,頭からテロだからダメというのは,何の理由付けにもなっていませんが。。世間的にはソレでは通らないのでしょうネ。。

ナニ？自衛隊がテロ弾圧にいく？寧ろテロの側に味方しろヨ的な。。。※)

　猪瀬クンも元々プロの政治家ではなかったし寧ろ権力を批判する側だった頃にはマトモに正直者だと思っていました。

　今は利権もからんでいて政治的参謀とかがいるのでしょうが。。

　私は原点に帰ってヤッタことはヤッタ,ヤラないものはヤラないと断固として正直に話して,ヤッタことのいくつかが現在の法律に照らして起訴に値し世論で非難されて失職したり罰金や実刑を受けるとしてもショウジキを貫徹してホリエモンのごとくそれらに甘んじるシカないと感じるのですが。。。

　他人を批判できるほどじゃないけど脱線するとスグにこうなります。。

原始根と指数(3)

　久しぶりですが,数論記事の続きです。

重要な次の３つ目の定理から始めます。

[定理3]：ｐを奇素数とし,ｎを１より大きい整数とする。

そして,ｐⁿの原始根の１つをｇとする。

このとき,ｇと(ｇ＋ｐⁿ)のうちの奇数である方が2ｐⁿの原始根

である。

(証明)：ｐは奇数なので,2とｐⁿは互いに素ですから,前々記事

で証明した互いに素な自然数の積に対するＥuler数の性質

から,φ(2ｐⁿ)＝φ(2)φ(ｐⁿ)＝φ(ｐⁿ)＝ｐⁿ－ｐ^n-1です。

そして,ａ∈Ｎが奇数なら,ａ^p-1≡1 (mod ｐⁿ)とａ^p-1≡1 (mod 2ｐⁿ)

は両方同時に成立するか,または両方共に不成立のいずれか

一方であることがわかります。

(※何故なら,ａ^p-1≡1 (mod ｐⁿ)ならａ^p-1＝1＋ｘｐⁿ；ｘ∈Ｚと書けますが

ａ∈Ｎが奇数という仮定からａ^p-1も奇数なのでｘｐⁿ＝ａ^p-1－1は偶数

です。

したがって,この場合ｘも偶数ですからａ^p-1≡1 (mod 2ｐⁿ)が成立します。

他方,ａ^p-1≡1 (mod ｐⁿ)が不成立なら,明らかにａ^p-1≡1 (mod 2ｐⁿ)

も不成立です。※)

さて,ｐⁿの原始根の１つｇに対してａ＝ｇ^{p^n-1}とおくと

ａ^p-1＝ｇ^{p^n-1(p-1)}＝ｇ^{φ(p^n)}ですが,ｇはｐⁿの原始根で,定義により

ｇ^{φ(p^n)}≡1 (mod ｐⁿ)が成立します。

したがって,ｇが奇数なら奇数の自然数ａとしてａ＝ｇ^{p^n-1}を

選択することができてａ^p-1≡1 (mod ｐⁿ)が成立するため同時に

ａ^p-1≡1 (mod 2ｐⁿ)も成立します。

すなわち,このときにはｇ^{φ(p^n)}＝ｇ^{φ(2p^n)}≡1 (mod 2ｐⁿ) となります。

他方,ｐⁿの原始根：ｇが偶数なら,(ｇ＋ｐⁿ)が奇数であり(ｇ＋ｐⁿ)は法ｐⁿ

ではｇと合同で,それ故,これもｐⁿの原始根であって,ｇ^{φ(p^n)}≡1 (mod ｐⁿ)

の成立と同時に(ｇ＋ｐⁿ)^{φ(p^n)}＝(ｇ＋ｐⁿ)^{p^n-1(p-1)}≡1 (mod ｐⁿも成立します。

それ故,このときは奇数：ａをａ＝(ｇ＋ｐⁿ)^{p^n-1(}とおけば前と同じく

ａ^p-1≡1 (mod ｐⁿ),および,ａ^p-1≡1 (mod 2ｐⁿ(ｇ＋ｐⁿ)が2ｐⁿの原始根

の１つを与えます。 (証明終わり)

これの具体例も簡単なものを１つ与えておきます。

(例)：ｐ＝29,ｎ＝1とします。

このとき,ｇ＝14はｐⁿ＝29¹＝29の原始根の１つです。

これはｇⁿ＝14²⁸≡1 (mod 29²)をも満たすことを前記事では見ました。

しかし,ｇ＝14は偶数なので,今証明した[定理3]によって,

2ｐⁿ＝2・29¹＝58の原始根ではなく,ｇ＋ｐⁿ＝14＋29＝43

が58の原始根です。

φ(58)＝φ(29)＝28であり,14²⁸≡1 (mod 29),かつ,43²⁸≡1 (mod 58)

が成立するはずです。

43は29²＝841の原始根でもありますが,これは奇数なので,

2・29²＝1682の原始根でもあります。

よって,φ(1642)＝φ(841)＝812より,43⁸¹²≡1 (mod 841),

かつ,43⁸¹²≡1 (mod 1682)が成立するはずです。

さて,次は重要な定理です。これによって,原始根が存在する整数の

全てのケースを挙げることができます。

これまでの考察はこれを示すための準備で,諸定理はこれの証明の

ための補助定理とも考えられるほどです。

[定理4]：自然数ｍについて法ｍの原始根が存在するのは

ｍ＝2,4,および,ｐを奇素数,ｎを自然数として ｍ＝ｐⁿ,または

ｍ＝2ｐⁿ と書ける場合に限られる。

(証明)：前記事で述べた[定理1]は,(ⅰ)2の原始根は1である。

(ⅱ)4の原始根は3である。(ⅲ)奇素数ｐの原始根は常に存在して,

その個数はφ(ｐ－1)個である。 　というものでした。

そこでｍ＝2,または4のときには確かにｍの原始根ｇが存在して,

それぞれｇ＝1,またはｇ＝3です。

唯一の偶素数2について,その2,4より大きいベキ乗数を,

ｍ＝2^k(ｋ＞2)とおくと,φ(ｍ)＝φ(2^k)＝2^k－2^k-1＝2^k-1(2－1)＝2^k-1

です。

このｍ＝2^k(ｋ＞2)に対して,(ａ,ｍ)＝1となる自然数ａ を取ると

ａは奇数ですから,ａ＝2ｔ＋1 (ｔ∈Ｚ)と書けます。

まず,ａ²＝(2ｔ＋1)²＝1＋4ｔ(ｔ＋1)≡1　(mod 8), そして,2＝2¹,8＝2³

です。

さらに,ａ⁴＝(2ｔ＋1)⁴＝(1＋8ｓ)²≡1　(mod 32), そして,4＝2²,32＝2⁵

です。

したがって,ａ²＝(2ｔ＋1)²≡1 (mod 2³),ａ⁴＝(2ｔ＋1)⁴≡1 (mod 2⁴),

ａ⁸＝(2ｔ＋1)⁸≡1 (mod 2⁵)..と続き,帰納的類推から,

ａ^{2^(k-2)}＝(2ｔ＋1)^{2^(k-2)}≡1 (mod 2^k)と予想されます。

実際,ａ^{2^(k-3)}＝(2ｔ＋1)^{2^(k-3)}≡1 (mod 2^k-1)と帰納的仮定を

与えると,ａ^{2^(k-3)}＝(2ｔ＋1)^{2^(k-3)}＝I＋2^k-1ｓ (ｓ∈Ｚ) と書けるため,

さらに両辺を２乗して,ａ ^{2^(k-2)}＝(2ｔ＋1)^{2^(k-2)}＝(I＋2^k-1ｓ)²

＝1＋2^kｓ(ｓ＋1)です。

これより,明らかに,ａ^{2^(k-2)}＝(2ｔ＋1)^{2^(k-2)}≡1 (mod 2^k)の成立

が導かれます。

ところが,ｋ＞2では2^k-2＜2^k-1＝φ(2^k)ですから,

結局,ｍ＝2^k(ｋ＞2)に対して(ａ,ｍ)＝1を満たす任意の自然数

ａがｍの原始根には成り得ないことが示されました。

よって ｍ＝2^k(ｋ＞2)の原始根は存在しません。

次に,ｍは合成数でｍ＝ｓｔ,ｓ＞2,ｔ＞2,(ｓ,ｔ)＝1とすると,前に証明した

Euler関数の性質から,φ(ｍ)＝φ(ｓｔ)＝φ(ｓ)φ(ｔ)です。

(※ちなみに,素数ｐについてはφ(ｐ)＝ｐ－1ですがφ(1)については,

φ(1)＝0ではなくφ(1)＝1であり,ｓまたはｔが1の場合も(ｓ,ｔ)＝1なら

φ(ｓｔ)＝φ(ｓ)φ(ｔ)は成立します。※)

ｓの素因数分解がｓ＝ｐ₁^α1ｐ₂^α2..ｐ_r^αr＝Π_j=1^rｐ_j^αj ；

α_j≧1(ｊ＝1,2,..,ｒ)かつ,ｐ_k≠ｐ_j (ｋ≠ｊ)と表現される なら,

φ(ｓ)＝Π_j=1^rφ(ｐ_j^αj)です。

そして,φ(ｐ_j^αj)＝ｐ_j^αj－ｐ_j^αj-1＝ｐ_j^αj-1(ｐ_j－1)です。

もしもｓが奇数なら,ｓ＝ｐ₁^α1ｐ₂^α2..ｐ_r^αr＝Π_j=1^rｐ_j^αjより,

ｐ_j^αjは全て奇数でｐ_jは奇素数なので,ｐ_j^αj-1は奇数ですが(ｐ_j－1)

は偶数であり,故にφ(ｐ_j^αj)は偶数です。

奇数：ｓ＝ｐ₁^α1ｐ₂^α2..ｐ_r^αr＝Π_j=1^rｐ_j^αjの素因数は少なくとも１つ

は奇素数のベキ因子を持つため,φ(ｓ)＝Π_j=1^rφ(ｐ_j^αj)も少なくとも

１つの偶数因子を持ちます。

それ故,ｓ＞2でｓが奇数ならφ(ｓ)は偶数です。

また,ｓが偶数でｓ＝ｐ₁^α1ｐ₂^α2..ｐ_r^αr＝Π_j=1^rｐ_j^αjの素因数のうち

の１つが2^k(ｋ＞2)の形のときも,φ(2^k)＝2^k－2^k-1＝2^k-1 は偶数

ですからφ(ｓ)は偶数です。

結局,φ(ｓ)が奇数なのはｓ＝1,2のとき,φ(1)＝φ(2)＝1 だけです。

そこで,ｍ＝ｓｔ,ｓ＞2,ｔ＞2,(ｓ,ｔ)＝1で,ｍが奇数でも 偶数でもφ(ｓ),

φ(ｔ)は共に偶数であり,もちろん, φ(ｍ)＝φ(ｓ(ｔ)＝φ(ｓ)φ(ｔ)も

偶数です。

それ故,φ(ｍ)/2,φ(ｓ)/2,φ(ｔ)/2は全て整数です。

しかも,(ａ,ｍ)＝1なる任意の整数ａに対して,

φ(ｍ)/2＝φ(ｓ)φ(ｔ)/2なので,Eulerの定理から

ａ^φ(m)/2＝(ａ^φ(s))^φ(t)/2≡1 (mod s),かつ,

ａ^φ(m)/2＝(ａ^φ(t))^{φ(s)/2φ(m)/2}≡1 (mod ｍ) を意味します。

φ(ｍ)＞0なので,明らかにφ(ｍ)/2＜φ(ｍ)ですから (ａ,ｍ)＝1

なる任意の整数ａはｍの原始根とは成り得ないことがわかりました。

したがってｍが合成数ならｍの原始根は存在しません。,

また,ｐが奇素数,ｎが自然数でｍ＝ｐⁿと書ける場合には,

あるｍの原始根ａ＝ｇが常に存在することは既にわかっています。

さらに,そのとき偶数のｍ＝2ｐⁿの形のｍについても,そのｇか,

または,(ｇ＋ｐⁿ)のいずれがｍの原始根となるきとが既に示されて

います。

以上から自然数ｍについて法ｍの原始根が存在するのは

ｍ＝2,4,および,ｐを奇素数,ｎを自然数としてｍ＝ｐⁿ,または

ｍ＝2ｐⁿ 2と書ける場合に限られることが示されました。

(証明終わり

まだ少しあるのですが前回,後１回で終わると書いた手前もあり

後ほんの少しなので,この記事に後から追加します。