« 無為徒食(畜生(ちくしょう))。。普通の日記 | トップページ | 新年明けましておめでとうございます。 »

2013年12月17日 (火)

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

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

と書きました。

 

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

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

  

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

します。

 

自然数:gが素数pの原始根なら,d|(p-1),かつd<(p-1)なる

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

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

  

また,もしもk<(p-1)なるkに対してgk≡1 (mod p)が成立するなら

gはpの原始根ではありません。

 

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

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

 

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

 

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

 

[補助定理]:(a,p)=1,(b,p)=1なるa,bについてそれらの法pにおける

位数をそれぞれ,x=ord(a), y=ord(b)とする。このとき,

 

(ⅰ ) (x,y)=1なら法pでのabの位数は,ord(ab)=xyである。

 

(ⅱ) (x,y)=d>1なら,法pにおいて,ord(c)=[x,y] なるcで(c,p)

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

 

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

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

 

(ⅰ) a≡1,b≡1より,(ab)xy=(a)(b)≡1 です。

 

そして,(x,y)=1なのでd=ord(ab)とすると,dは互いに素なxとyの約数

である2つの因数の積に分解できて,d=d121|x,d2|y,(d1,d2)=1と

表わすことができます。

 

それ故,x=x11,および,y=y12と書けば,(ab)=(ab)d1d2≡1 です。

 

この両辺をx1乗すると,{(ab)d1d2}x1=axd2xd2≡1なので

xd2≡1を得ますが,y=ord(b)なのでy|(xd2)です。

 

ところが,y=y12なのでy1|xですが,(x,y)=1よりy1=1です。

 

同様に,{(ab)d1d2}x2=ayyd1yd1≡1 から x1=1 を得ます。

 

したがって,d=ord(ab)xy=xyです。

(ⅱ)x0|xなら{a(x/x0)}x0=a≡1です。

  

そこで,{a(x/x0)}≡1でk<x0ならk|x0ですから,

(x/x0)kが整数でa(x/x0)k≡1,かつ(x/x0)k≦x

となります。

 

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

0はa(x/x0)の位数です。

 

同様にy0|yならy0はb(y/y0)の位数です。

 

そこで,d=(x,y)>1の場合

x'=x/d,y'=y/dとおくと(x',y')=1で,かつ,

x'=ord(a),y'=ord(b)なので,

 

今証明したばかりの(ⅰ)によりx'y'=ord(a)です。

 

それ故,a=(ab)であり(ab)dx’y’≡1です。

 

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

[x,y]=dx'y'です。

 

こで,c=aαβ(α,β∈,1≦α≦d,1≦β≦d)なる

形式のcの中にord(c)=dx'y'=[x,y],を満たすもの

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

 

例えば,c=abとおけば法pでcdx'y'≡1です。

 

そして,k≦dx'y',かつ,c=adkk≡1なら,

|(dx'y')ですからd=d12,x'=x12 ,

y'=y12としてk=d111と表現されます。

 

このとき.c=adkk≡1はadd1x1y1d1x1y1≡1

と書けます。

 

最後の合同式の両辺をx2乗するとb1xy11です。

 

故に,y=ord(b)よりy≦(d1xy1)であり

y|(d1xy1)です。

 

そこで,y=dy'=dy12ですから(dy2)|(d1x)ですが,

(x,y2)=1より,結局,(dy2)|d1,つまり,(d22)|1を得ます。

 

したがって,d22=1である他なく.自然数の範囲ではd2=y2=1です。

 

よってk=dx'y'でありord[c]=dx'y'=[x,y]が得られました。

(証明終わり)

 

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

適用した1例です。

 

[例]:素数がp=191とすると(a,191)=1ならFermatの小定理

により,p-1=a190≡1 (mod 191)です。

 

そして,a=2とすると2190≡1 (mod 191)であり,それ故,

295≡±1 (mod 191)です。

 

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

 

(※何故なら, 295=(25)19,ですが, 29=512=191×2+130,

210=1024=191×5+69から219≡69×130=8970=191×47-7,

295≡(-7)5=-16807=-191×88+1≡1 を得るからです。

 

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

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

 

pが素数で(a,p)=1のとき,

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

(p-1)が偶数なので(p-1)/2は整数です。

 

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

σ(a)=a(p-1)/2≡±1 (mod p)です。

 

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

Legendreの記号:(a/p)=σ(a)=a(p-1)/2≡±1 (mod p)

を導入すると,

 

(ab/p)=(a/p)×(b/p)が成立します。

 

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

(p/q)(q/p)=(-1)(p-1)(q-1)/4であり,それ故に,

(p/q)=(q/p)(-1)(p-1)(q-1)/4というものです。

 

一方,(2/p)=(-1)(p^2-1)/8という法則から,

(2/19)=(-1)45=-1,(2/5)=(-1)3=-1という情報

が得られます。

 

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

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

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

295≡1という考察も可能でしょう。

 

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

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

 

一方,b=7とすれば710≡1 (mod 191),y=ord(7)=10 です。

 

(x,y)=(95,10)=5=d>1,x1=x/5=19,y1=y/5=2,

295=(25)19≡1 (mod 191),710=(75)2≡1 (mod 191),

(x1, y1)=(19,2)=1,[x,y]=x11d=19×2×5=190

 

(25×75)38≡1 (mod 191),(19,10)=1,[x,y]=dx11=190

(25×7)190≡1 (mod 191)であり,

 

25×7=32×7=214=191+33=33 (mod 191),

そこで33190≡1 (mod 191)です。

 

したがって,g=33はp=191の1つの原始根です。

 

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

紹介します。

 

例から述べます。

 

素数pをp=7とするとg=3.5はpの原始根です。

 

mod7では3≡3,32≡2,33≡6,34≡4,35≡5,36≡1,

また 5≡5,52≡4,53≡6,54≡2,55≡3,56≡1です。

 

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

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

 

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

 

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

とする巡回群である。

 

(証明):g0=1,g,g2,..,gp-2,gp-1≡1 (mod p)です。

 

1,g,g2,..,gp-2は全て異なる(p-1)個の元ですから明らかに

{1,g,g2,..,gp-2}={12,..,p-1}=,(/p)×を得ます。

 

(証明終わり)

 

そこで,上記例の1つのg=5の例において

51≡5,52≡4,53≡6,54≡2,55≡3,56≡1 (mod 7)を,

それぞれ,Ind55=1,Ind54=2,Ind56=3,Ind52=2,

Ind53=5,Ind51=6と書くことにします。

 

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

 

[定義]:素数pの原始根gに対してg≡a(mod p)のとき,

Ind(a)=kと書き,これをgを底としたaの指数,または

離散対数という。

 

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

 

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

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

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

ここで終了します。

|

« 無為徒食(畜生(ちくしょう))。。普通の日記 | トップページ | 新年明けましておめでとうございます。 »

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

コメント

コメントを書く



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




トラックバック


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

« 無為徒食(畜生(ちくしょう))。。普通の日記 | トップページ | 新年明けましておめでとうございます。 »