« 訃報 島倉千代子さん。。。 | トップページ | 最近の生活スタイル »

2013年11月10日 (日)

原始根と指数(1)

 退院して1ヶ月余り,やっと,科学記事復活第1弾です。

 

 こういうものを投稿しないと,私のブログが完全復活したという気がしません。

 

 何故か,6年前の心臓病,心臓手術での入院以来,病室で読む専門書は

 普段敬遠している数学関係が多くなっています。

 

 今回も何を思ったか,「「フェルマー(Fermat)予想」。。

 今は,1994年:Wills(ワイルズ)により証明されたので,「フェルマーの大定理」

 あるいは,「フェルマーの最終定理」ですが,

 

 この証明をいつの日かじっくり鑑賞できるようになりたいな。。などと

 考えた結果,今まで知っている数論,整数論についての僅かな知見を

 楕円曲線なども含めて,もう少し広げたいなどと思いました。

 

 自宅から病室に持参したのはブルーバックスの「数論入門」(芹沢 正三 著)

 と岩波書店の「数論入門(楕円曲線)」(J.S.Chahal著;織田 進 訳)の2つです。

 

 入院後,最初に読み始めたのは後者の方で,ときどき気分転換に前者

 を読んでいました。

 

 しかし,今回の記事のテーマとして採用したのは前者のブルーバックス

 の方です。

 

 病室では参考書が全く無いので帰宅してから少し補足しています。

 

 時間は有り余っていたので両書とも穴のあくほど精読して読了しました

 が,目標にはまだまだですね。イヤ,その前に寿命が。。。

 

 さて,本文に入ります。

 

 まず,有名なGaussの合同式に関する「Fermatの小定理」から始めましょう。

 

 これは,,"素数pに対して(a,p)=1ならap-1≡1 (mod p)が成り立つ。"

 というものです。

 

 しかし,1≦k<(p-1)なるkでak≡1 (mod p)となる場合もあります。

 

 そこで,ak≡1 (mod p)を満たす最小の自然数kをpを法とするaの位数(order)

 といい,これを|a|,または,ord(a)と表わすことにします。

 

 例えば,p=7,a=4なら(a,p)=(4,7)=1ですが,p=7を法として,またはmod 7

 で41≡4,42≡2,43≡1,44≡4,45≡2,46≡1ですから,ap-1=46≡1 (mod 7)です。

 

 確かにFermatの小定理は成立していますが,その前に43≡1 (mod 7)と

 なっていますね。

 

 それ故,p=7を法とする4の位数;ord(4)は,6=p-1ではなく 3です。

 

 そこで,特に,(a,p)=1でaの位数がord(a)=p-1であるようなaをpの原始根

 (primitive root)と定義します。

 

 つまり,1≦k<(p-1)なるkでは,ak≡1 (mod p)とはならず,k=p-1で初めて

 ak=ap-1≡1 (mod p)となるようなaをpの原始根と呼ぶわけです。

 

 この原始根:aを特にgと表わすことがあります。

 

 例えば,p=7,a=3なら(a,p)=(3,7)=1であり,

 7を法として,,31≡3,32≡2,33≡6,34≡4,35≡5,36≡1ですから

 3は7の1つの原始根です。

 

 ここで,Fermatの小定理と並んで合同式の代表的な定理であるEuler

 の定理も便宜上必要なので,これの説明のため,Euler関数という整数

 の関数を与えます。

 

 以下,を整数全体,を自然数(正整数)全体を示す集合します。,

 

 1≦k≦nでnと互いに素:(k,n)=1であるk∈nの個数はnの関数の1つ

 となるので,これをφ(n)と書き, Euler関数と呼びます。

 

 特にp∈が素数のときはk=1,2、..,p-1が全てpと互いに素なので,

 φ(p)=p-1です。

 

  また,p,qが共に素数でp<qならn=pqを超えないnと互いに素 でない

 自然数は,p,2p,3p,..,qpのq個とq,2q,..,pqのp個から 共通するqp=pq

 を除いた(p+q-1)個です。

 

 そこでφ(n)=φ(pq)=pq-(p+q-1)=(p-1)(q-1)=φ(p)φ(q)

 となります。

 また,もしもq=pでn=pq=p2なら,nと互いに素でない自然数は

 ,p,2p,3p,..,p2のp個ですからφ(n)=Φ(p2)=p2-pです。

 

 一般に,nが素数pのベキ:αを自然数としてn=pαなら,nと互いに素で

 ない自然数の個数はpα-1ですから,φ(n)=Φ(pα)=pα-pα-1です。

 実は,(m,n)=1ならφ(mn)=φ(m)φ(n)である。という法則がありますが,

 これは1995年(45歳当時)に「代数系入門」を1冊精読したときのノートの

 (補題E)に相当します。

 

 このノートから引用した,これの証明を書いておきます。

 

※(証明):S,T,Uをそれぞれ法m,n,mnに関する完全剰余系,

 S,T,Uを同じ法m,n,mnに関する既約剰余系とします。

 

 ただし法mに関する完全剰余系とは法mに関する合同関係から作られる

 全ての同値類=剰余類:Caの代表元aの集合です。

 つまり,S={0,1,..,m-1}={-1,..,-m+1,0}etc. です。

 

 一方,既約剰余系とは,(a,m)=1であるような剰余類=既約剰余類 C

 の代表元aの集合で,その位数=既約剰余類の個数はφ(m)です。

 

 このとき,完全剰余系の定義から,z∈Uなら, z≡x (mod m),かつ,

 z≡y (mod n)なる,x∈S,y∈Tが存在します。

 

  何故なら,∀z∈Uに対して,明らかにx’≡z(mod m)なるx’が存在しますが,

 このx’はmに関する剰余類のどれかに属しはそれら剰余類の直和です

 から,∃x∈S:x≡x’(mod m)です。

 

 そして,完全剰余系の定義から,y∈S,y≠xならy≡x’とは成り得ないため,

 x≡z (mod m)を満たす一意的なx∈Sが存在します。

 

 同様にy≡z (mod n)を満たす一意的なy∈Tが存在します。

 

  逆に,(m,n)=1なので,∀(x,y)∈S×Tに対して, 合同式の方程式::

 z≡x (mod m),かつ,z≡y (mod n) は,mnを法として一意的な解zを

 持つこともわかります。

 

 そして,z∈Uと(x,y)∈S×Tの一意的対応において

 (z,mn)=1は,(z,m)=1,かつ(z,n)=1と同値です。

 

  つまり,(z,mn)=1は(x,m)=1,かつ(y,n)=1と同値です。

 

 したがって,z∈Uと(x,y)∈S×も完全に1対1に対応します。

 

 以上から,φ(mn)=φ(m)φ(n)が得られました。(証明終わり)

 

 例えば,p=3,q=7ならn=pq=21と互いに素でない自然数は

 6,9,12,15,18,7,14,21の9個です,から,その個数はp+q-1です。

 

 そして,φ(21)=φ(pq)=pq-(p+q-1)=(p-1)(q-1)

 =2×6=12です。

 

 nの素因数分解がn=pαβγ..ならそのEuler関数は,

 φ(n)=φ(pα)φ(qβ)φ(rγ)..=(pα-pα-1)(qβ-qβ-1)(rγ-rγ-1)..

 =pαβγ..,(1-1/p)(1-1/q)(1-1/r).. =n(1-1/p)(1-1/q)(1-1/r)..

 と書けます。

 

 さらに,Euler関数について,有名な法則があります。

 

 すなわち,任意の自然数nの約数dについてφ(d)の総和はnに等しい。

 つまり,Σd|nφ(d)=nである。という法則です。

 

 これも証明しておきます。(ただし,d=1もnの約数として勘定に入れます。)

 

 (証明):1,nも含めたnの全ての約数をd1,d2,..dj,..とします。

 

 そして,n=d11’=d22’=..=djj’=..と書きます。

 

 すると,x=1,2,..,nのn個のxのうちで,xがd1の倍数であって,

 かつ,(x,n)=d1であれば(x, d1’)=1です。

 

 また,逆に,(x, d1')=1のとき,nをd1'で割った商をd1と書けば,

  n=d11'で,かつ,(x,n)=d1,です。

 

 そして,こうしたxの個数は丁度, φ(d1')です。

 

 同様に,(x,n)=d2,(x, d2')=1なるxの個数はφ(d2')です。

 

  結局,x=1,2,..,nのn個のxの各々は最大公約数が(x,n)=djのどれか

 に属し,φ(d1'),φ(d2'),..,φ(dj')..がnの分割となっています。

 

 すなわち,n=φ(d1’)+φ(d2’)+..+φ(dj’)+..,あるいは

 Σjφ(dj')=n です。

 

 全てのnの約数d(nを割り切る数d:d|n)の集合:{d1,d2,..dj,..} は:

 {{d1’,d2’,..dj’,..}と一致しますからΣkφ(dk)=Σjφ(dj’)=nであり,

 結局,Σd|nφ(d)=nと書けます。(証明終わり)

 

 「Eulerの定理」:(a,m)=1ならaφ(m)≡1 (mod m), および,

 「Fermatの小定理」:pが素数で(a,p)=1ならap-1a≡1 (mod m),

 については,既に当ブログ過去記事で証明済みなので証明は省略します。

 

 さて,ak≡1 (mod p)を満たす最小の自然数kをpを法とするaの位数,といい

 |a|,またはord(a)と表わし,特に(a,p)=1でaの位数がp-1であるようなaを

 素数pの原始根と呼ぶ。と先に述べましたが,

 

 この素数pの原始根の定義を,素数とは限らない一般の正整数mのケース

 に拡張します。

 

 すなわち,ak≡1 (mod m)を満たす最小の自然数kをmを法とするaの

 位数といい,(a,m)=1のときaの位数がφ(m)に等しいようなaをmの

 原始根と呼ぶ。と定義します。

 

 特に原始根であることを強調したいときにはaでなくgと書くこともあります。

 

 簡単な定理を証明しておきます。

 

 [定理]:m∈,(a,m)=1とする。a≡1 (mod m)なら,dはaの位数:ord(a)

 で割り切れる。特に,aの位数はφ(m) の約数に限られる。

 

 (証明):a≡1 (mod m),かつ,aord(a)≡1 (mod m)なので,

 d=q・ord(a)+r (0≦r<ord(a))とするとa≡1 (mod m)ですが,

 ord(a)はa≡1 (mod m)を満たす最小の正整数kですからr=0 です。

 

 それ故,d=q・ord(a)よりdはaの位数ord(a)で割り切れます。

 

 特に, Eulerの定理から(a,m)=1ならaφ(m)≡1 (mod m)なのでaの位数

 ord(a)はφ(m)の約数であることが必要です。(証明終わり)

 

 遅筆なので,今日のところはここまでにします。

 

 参考文献:芹沢正三  著 「数論入門」(講談社ブルーバックス)

        松坂和夫 著 「代数系入門」(岩波書店):

 

 PS:最近は慣れましたが,やや長めの記事草稿をWordでテキストベース

 でオフラインで作成したものをココログにコピーしてHTMLに翻訳しアップ

 すると余計な尾ひれで文字化けや文字のサイズなどが変化して整形して

 編集するのに手まどることが多いです。

 

 その上,作業中にWindowsがフリ-ズして徒労が重なるとイヤになって

 当分そのまま放置したくなりますね。

|

« 訃報 島倉千代子さん。。。 | トップページ | 最近の生活スタイル »

303. 代数学・数論」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 原始根と指数(1):

« 訃報 島倉千代子さん。。。 | トップページ | 最近の生活スタイル »