« 最近の生活スタイル | トップページ | 原始根と指数(3) »

2013年11月28日 (木)

原始根と指数(2)

ずいぶん,間が開きましたが数論の記事の続きです。

 

今年は半年近くも入院療養していてその方が日常化していたので

自宅における日常生活の私本来の精神はまだリハビリ中のような

気分が続いています。

 

よほど,精神的余裕があってテンションが上がらないとブログを

書こうという気分にさえなれず,PC中毒は相変わらずですが,パソ

コンに向かうと,ついネット将棋とか安易な娯楽の道に耽溺して

しまいそうです。

 

まあ,身体も心も日常性を取り戻すのはボチボチですね。

 

(※それにしてもブログのテンプレート何とかならないかなあ。。

 

ここ@niftyのココログがブログにしては長く複雑な数式のアップ

にも対応できて表示も見みやすいと思っているので,ずっと愛用

してきましたが,何故か昔と違ってオカシイです。

 

文字の大きさを均等にするくらい自分でHTMLをいじらなくても

自動的にやってくれれば。。と思います。

 

ときどき,編集やる気をなくして放置したくなります。。)

  

さて,まず,原始根の定義を再確認しておきましょう。

 

[定義]:(原始根;primitive root)

aをある整数とするとき,ak≡1 (mod m)を満たす最小の自然数k

をmを法とするaの位数(order)と呼び,これをord(a)で表わす。

 

特に(a,m)=1で,aの位数ord(a)がmのオイラー数:φ(m)に

等しいような整数aをmの原始根という。

 

さて,次に,任意の正整数mに対して原始根が必ず存在することを

示すため,次の定理の成立を証明します。

※以下では便宜上,整数といえば正整数(自然数)を指すものと

します。特に,原始根も自然数のそれとします。

 

その前にまず,定理の証明に必要な補助定理(lemma)を与えます。

  

[補助定理]:(Lagrangeの定理)

素数pを法とするn次合同方程式の根の個数は法p(mod p)で

nを超えない。

 

(証明):数学的帰納法(induction)に頼ります。

 

まず,n=1の1次合同方程式:ax+b≡0 (mod p)は唯1つ

の解を持つか,解がないかのいずれかであることは明らかです。

 

n≧2のとき,(n-1)次のときには定理の命題が成立すると仮定し,

n次の場合の命題の成立を証明します。

 

すなわち,f(x)をxの任意のn次多項式として,n次合同方程式:

f(x)≡0 (mod p)の根を考えます。

 

これの根が存在しないなら根の個数はゼロなので根の個数がnを

超えないのは明らかですからこれで証明終了です。

 

一方,1つでも根があればそれをx1とします。

 

するとf(x1)≡0 (mod p)ですからf(x)≡0 (mod p)は,

f(x)≡f(x)-f(x1)≡0 (mod p)と同値になりますが,

 

明らかに,これはf(x)-f(x1)=(x-x1)g(x);

ただし,g(x)はxの(n-1)次多項式,と因数分解されます。

 

そこで,,f(x)≡0 (mod p)は,(x-x1)g(x)≡0 (mod p)

を意味することになります。

 

さらに,f(x)≡0 (mod p)にx1と合同でない別の根x2がある

とすればf(x2)≡(x2-x1)g(x2)≡0 (mod p)となりますが,

2-x1≡0 (mod p)ではないのでg(x2)≡0 (mod p)です。

 

つまり,f(x)にx=x1と異なる根があればそれはg(x)の根です。

 

g(x)は(n-1)次多項式であり,(n-1)次については定理の命題

が成立すると仮定しているので,g(x)≡0 (mod p)を満たす根の個数

は(n-1)を超えません。

 

したがって,x=x1を加えてn次合同方程式f(x)≡0 (mod p)

を満たす解の個数はnを超えません。(証明終わり)

 

この補助定理を用いて証明すべき定理は次の通りです。

 

[定理1]:(ⅰ)2の原始根は1である。(ⅱ)4の原始根は3である。

(ⅲ)奇素数pの原始根は常に存在して,個数はφ(p-1)個である。

 

(証明):pが素数のときはφ(p)=p-1なので,aが原始根である

ことはaの位数がp-1:ord(a)=p-1であることを意味します。

 

(ⅰ)m=p=2ならp-1=1でありap-1=a≡1(mod 2)となるaは

2を法として1のみであるのは明らかです。

 

いいかえると,奇数aは全て原始根ですがp=2を法とする整数と

いう意味ではa=1のみです。

 

(ⅱ)m=4のときはφ(m)=φ(4)=2です。

 

1,2,3,4のうち,a≡1(mod 4)は成立せずa2≡1(mod 4)となるaは

明らかにa=3だけです。

 

(ⅲ)m=p(奇素数)のとき

 

dをφ(p)=p-1の任意の約数とします。

 

もしも位数がdの整数が存在すれば,それをbとすると,位数の

定義から,b≡1 (mod p)であり,k<dならbk≡1(mod p)は

成立しません。

 

そして,法pではbのベキ乗は1=b0,b,..,bd-1に限られます。

 

これらd個は全て,(bj)≡1(mod p)(j=0,1,..,d-1)を満たす

ので,xd≡1 (mod p)の解xです。

 

ところが,上の補助定理(Lagrangeの定理)によればxd≡1 (mod p)

or xd-1≡0 (mod p)を満たすpを法とする解xの個数は高々d

です。

 

しかも,i,j=0,1,..,d-1でi≠jかつ,bi≡bj (mod p)なら

|i-j|≡1 (mod p),かつ,0<|i-j|<dとなり,dが位数である

という仮定に矛盾します。

 

そこで,xd-1≡0 (mod p)の解:1=b0,b,..,bd-1は全て法p

について互いに合同ではないd個ですから,これらがx≡1 (mod p)

の解の全てです。

 

これらのうちの任意の1個のbjの位数をeとすると,(bj)

≡bje≡1 (mod p)なので,d|(je):つまり,je≡0 (mod d)

です。

 

ここで,g=(j,d)とおくと,j=j1g,d=d1g,(j1,d1)=1

ですから,je≡0 (mod d )というのは,j1ge≡0 (mod d1g)を

意味します。

 

平たくいえば,j1geはd1gの倍数です。

 

そこで,gで割ってj1eがd1の倍数というこということに

なりますが,(j1,d1)=1なので,結局,eがd1の倍数です。

 

すなわち,d1|eでありd1≦eです。

 

他方,(bj)d=(bd)j≡1 (mod p)ですが,eがbjの位数である

と仮定したのでe≦dです。

 

したがって,もしもg=(j,d)=1であり,それ故,d1=d/g=d

であれば,e|d1,e≦d1となり,d1≦eかつe≦d1より,

e=d1=dとなるため,bjの位数eはdに一致します。

 

逆に,eは常にd1の倍数ですが,それが特にdの倍数となるのは

g=(j,d)=1のときのみですからeがdに一致するのは,

g=(j,d)=1のときに限られます。

 

それ故,φ(p)=p-1の任意の約数dに対して,ある整数bの位数

がdなら,それから得られる異なるd個のベキ:

1=b0,b,..,bd-1のうち,位数がdである元の個数はφ(d)です。

 

したがって,特にd=φ(p)=p-1のとき,{b0,b,..,bp-2}

は,{1,2,..,p-1}と一致しφ(p)=p-1を位数とする元:

つまり,原始根の個数はφ(p-1)個です。(証明終わり)

 

次に着目したのは素数のベキの原始根に関する次の定理です。

 

[定理2]:gを素数pの原始根,nを1より大きい整数とすると,

m=pnの原始根は常に存在する。

 

そして,次が成立する。

 

(a)gφ(p)=gp-1≡1(mod p2)が満たされな場合

gはm=pnの1つの原始根である。

 

(b)gφ(p)=gp-1≡1(mod p2)が満たされる場合

gはm=pnの原始根ではないが,(g+p)はm=pnの1つの原始根

である。

 

(証明):m=pnに対してはφ(m)=φ(p)=p-pn-1

=pn-1(p-1)ですから,mの原始根gとは位数がpn-1(p-1)

に等しい整数を意味します。

 

さて, 一般性を損なうことなく,pの原始根gは自然数である

とします。

 

gは素数pの原始根ですから,(g,p)=1,または{1,2,..,p-1}

の元の1つです。

 

そこで,gp-1≡1 (mod p)は当然成立していますが,

p-1≡1 (mod p2)とは限りません。場合分けをします。

 

(a)gp-1≡1 (mod p2)が満たされない場合

 

p-1≡1 (mod p)より,あるゼロでない整数xによって

p-1=1+xp,かつ(x,p)=1 と書けます。

 

これから,gp-1のp乗の二項展開:gp(p-1)=(1+xp)

=Σr=0ppr(xp)rによって,gp(p-1)≡1+p2x (mod p3)

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

 

さらに,p乗してgp^2(p-1)=(1+xp)p^2≡1+p3x (mod p4)

を得ます。

 

両辺のp乗の繰り返しから,帰納的に,

p^(n-2)(p-1)≡1+pn-1x(mod pn) (n≧2)となり,

それ故,gp^(n-1)(p-1)≡1 (mod pn) (n≧2)を得ます。

 

そして,d<(p-1)で,かつd|(p-1)とするとき,

 

もしも,gd・p^(n-1)≡1 (mod pn)(n≧2)なら,

d・p^(n-1)≡1 (mod p)から,gd≡1 (mod p)となり

gがpの原始根であるという仮定に矛盾します。

 

何故なら,gp-1≡1 (mod p)より(gp)p≡gp^2≡gp≡g (mod p)

であり,これを繰り返してgp^(n-1)≡g (mod p)を得ます。

 

故に,gd・p^(n-1)=(gp^(n-1))d≡gd (mod p)ですが,

d・p^(n-1)≡1 (mod pn)なら,gd・p^(n-1)≡1 (mod p)

なので,gd≡1 (mod p)となり,gの位数がd以下となるので

仮定に矛盾します。

 

故に,gがpの原始根ならd<(p-1)に対して

d・p^(n-1)≡1 (mod pn)となることはなく,

他方,gp^(n-1)(p-1)=gφ(p^n)≡1 (mod pn)です。

 

したがって,この場合,gはm=pnの1つの原始根です。

 

(b)gp-1≡1 (mod p2)が満たされる場合

 

(p-1)<p(p-1)=φ(p2)なので,gはp2の原始根では

ありません。

 

そして,gp-1=1+xp2と書けるので,両辺をp乗して二項展開

を見ることから,gp(p-1)=1+xp3≡1 (mod p3)です。

 

以下,両辺のp乗を繰り返して帰納的に,

p^(n-2)(p-1)=1+xpn≡1 (mod pn)が成立します。

 

しかし,pn-2(p-1)<pn-1(p-1)=φ(pn)なので

gはm=pnの原始根ではありません。

  

ところが,gp-1≡1 (mod p)なので,法pではgと合同な元

に過ぎない(g+p)を考えると,

 

(g+p)p-1=gp-1+Σr=1p-1p-1rrp-1-r≡1 (mod p)

であって,これももちろんpの原始根です。

 

右辺の二項展開から明らかに法p2では,(g+p)はgと

合同ではなく(g+p)p-1≡1 (mod p2)は成立しません。

 

そこでg'=g+pを改めてpの1つの原始根gと見ると,これは

条件(a)を満たすpの原始根となるため,これはm=pnの原始根

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

 

たった今証明した[定理2]の具体例を与えておきます。

 

(例1):p=7については,g=3が1つの原始根であることは

既に前記事で見ました。

 

そして32=9≡2(mod 7)より,確かに36≡8≡1(mod 7)ですが,

34=81≡32 (mod 49)より,36≡32×9≡43 (mod 49)なので,

36≡32×9≡1 (mod 72)は成立しません。

 

一方,φ(72)=42であり,Eulerの定理により,もちろん,

342≡1(mod 72)は成立します。

 

したがって,上に示した定理2から3は72の原始根であるだけ

でなく,73,74,.など全ての7のべき乗の原始根です。

 

(例2):p=29については(14,29)=1なのでFermatの小定理

が成立して1428≡1 (mod 29)でありg=14はp=29の原始根

と成り得る資格があります。

 

面倒ですが実際に計算してみると,確かにg=14が1つの原始根

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

 

一方,φ(292)=28×29=812で,Eulerの定理により

14812≡1 (mod 292)です。

 

292=841であり,法841では142=196,143=196×14≡221

144=196×196≡571,146≡571×196≡63,148≡571×571≡574,

1414≡574×63≡840≡-1です。

 

そこで,1428≡1 (mod 292)なので,14は292の原始根ではない

ですが,g+p=14+29=43が292,293,294,.など全ての29の

べき乗の原始根です。

 

※ほんの少しのテーマで入院中には1日か2日で通過したところ

なのに,退院後の今,ブログ記事にするのに,怠惰もあって1ヶ月

以上もかかってますが,まだ,続きがあるので後1回このテーマに

お付き合いください。

 

PS:年内は,午後の仕事場への出勤前に,要介護1で月水金には

介護ヘルパーが来て簡単な家事を1時間やって頂き,そしてほぼ

毎日看護師が来て,私の体温,血圧,血糖値などチェック,さらに

足の傷の洗浄とケア,治療をして頂いています。

 

自分の部屋なのに,まるで個室入院の延長であるかのような健康

的な状態が続いていて,不潔で不規則,自堕落な生活のほうが性に

合う?はずの私の精神の方が崩壊するのではないか?と心配です。

|

« 最近の生活スタイル | トップページ | 原始根と指数(3) »

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

コメント

コメントを書く



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




トラックバック


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

« 最近の生活スタイル | トップページ | 原始根と指数(3) »