« 原始根と指数(2) | トップページ | 無為徒食(畜生(ちくしょう))。。普通の日記 »

2013年12月 6日 (金)

原始根と指数(3)

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

 

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

 

[定理3]:pを奇素数とし,nを1より大きい整数とする。

そして,pnの原始根の1つをgとする。

 

このとき,gと(g+pn)のうちの奇数である方が2pnの原始根

である。

 

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

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

から,φ(2pn)=φ(2)φ(pn)=φ(pn)=pn-pn-1です。

 

そして,a∈が奇数なら,ap-1≡1 (mod pn)とap-1≡1 (mod 2pn)

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

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

 

(※何故なら,ap-1≡1 (mod pn)ならap-1=1+xpn;x∈と書けますが

a∈が奇数という仮定からap-1も奇数なのでxpn=ap-1-1は偶数

です。

 

したがって,この場合xも偶数ですからap-1≡1 (mod 2pn)が成立します。

 

他方,ap-1≡1 (mod pn)が不成立なら,明らかにap-1≡1 (mod 2pn)

も不成立です。※)

 

さて,pnの原始根の1つgに対してa=gp^n-1とおくと

p-1=gp^n-1(p-1)=gφ(p^n)ですが,gはpnの原始根で,定義により

φ(p^n)≡1 (mod pn)が成立します。

 

したがって,gが奇数なら奇数の自然数aとしてa=gp^n-1

選択することができてap-1≡1 (mod pn)が成立するため同時に

p-1≡1 (mod 2pn)も成立します。

 

すなわち,このときにはgφ(p^n)=gφ(2p^n)≡1 (mod 2pn) となります。

 

他方,pnの原始根:gが偶数なら,(g+pn)が奇数であり(g+pn)は法pn

ではgと合同で,それ故,これもpnの原始根であって,gφ(p^n)≡1 (mod pn)

の成立と同時に(g+pn)φ(p^n)=(g+pn)p^n-1(p-1)≡1 (mod pnも成立します。

 

それ故,このときは奇数:aをa=(g+pn)p^n-1(とおけば前と同じく

p-1≡1 (mod pn),および,ap-1≡1 (mod 2pn(g+pn)が2pnの原始根

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

 

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

 

(例):p=29,n=1とします。

 

このとき,g=14はpn=291=29の原始根の1つです。

これはgn=1428≡1 (mod 292)をも満たすことを前記事では見ました。

 

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

2pn=2・291=58の原始根ではなく,g+pn=14+29=43

が58の原始根です。

 

φ(58)=φ(29)=28であり,1428≡1 (mod 29),かつ,4328≡1 (mod 58)

が成立するはずです。

  

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

2・292=1682の原始根でもあります。

 

よって,φ(1642)=φ(841)=812より,43812≡1 (mod 841),

かつ,43812≡1 (mod 1682)が成立するはずです。

  

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

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

   

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

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

 

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

m=2,4,および,pを奇素数,nを自然数として m=pn,または

m=2pn と書ける場合に限られる。

  

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

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

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

 

そこでm=2,または4のときには確かにmの原始根gが存在して,

それぞれg=1,またはg=3です。

 

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

m=2k(k>2)とおくと,φ(m)=φ(2k)=2k-2k-1=2k-1(2-1)=2k-1

です。

 

このm=2k(k>2)に対して,(a,m)=1となる自然数a を取ると

aは奇数ですから,a=2t+1 (t∈)と書けます。

 

まず,a2=(2t+1)2=1+4t(t+1)≡1 (mod 8), そして,2=21,8=23

です。

 

さらに,a4=(2t+1)4=(1+8s)2≡1 (mod 32), そして,4=22,32=25

です。

 

したがって,a2=(2t+1)2≡1 (mod 23),a4=(2t+1)4≡1 (mod 24),

8=(2t+1)8≡1 (mod 25)..と続き,帰納的類推から,

2^(k-2)=(2t+1)2^(k-2)≡1 (mod 2k)と予想されます。

 

実際,a2^(k-3)=(2t+1)2^(k-3)≡1 (mod 2k-1)と帰納的仮定を

与えると,2^(k-3)=(2t+1)2^(k-3)=I+2k-1s (s∈) と書けるため,

さらに両辺を2乗して,a 2^(k-2)=(2t+1)2^(k-2)=(I+2k-1s)2

=1+2ks(s+1)です。

 

これより,明らかに,a2^(k-2)=(2t+1)2^(k-2)≡1 (mod 2k)の成立

が導かれます。

  

ところが,k>2では2k-2<2k-1=φ(2k)ですから,

結局,m=2k(k>2)に対して(a,m)=1を満たす任意の自然数

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

 

よって m=2k(k>2)の原始根は存在しません。

 

次に,mは合成数でm=st,s>2,t>2,(s,t)=1とすると,前に証明した

Euler関数の性質から,φ(m)=φ(st)=φ(s)φ(t)です。

 

(※ちなみに,素数pについてはφ(p)=p-1ですがφ(1)については,

φ(1)=0ではなくφ(1)=1であり,sまたはtが1の場合も(s,t)=1なら

φ(st)=φ(s)φ(t)は成立します。※)

 

sの素因数分解がs=p1α12α2..prαr=Πj=1rjαj

αj≧1(j=1,2,..,r)かつ,pk≠pj (k≠j)と表現される なら,

φ(s)=Πj=1rφ(pjαj)です。

 

そして,φ(pjαj)=pjαj-pjαj-1=pjαj-1(pj-1)です。

 

もしもsが奇数なら,s=p1α12α2..prαr=Πj=1rjαjより,

jαjは全て奇数でpjは奇素数なので,pjαj-1は奇数ですが(pj-1)

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

 

奇数:s=p1α12α2..prαr=Πj=1rjαjの素因数は少なくとも1つ

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

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

 

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

 

また,sが偶数でs=p1α12α2..prαr=Πj=1rjαjの素因数のうち

の1つが2k(k>2)の形のときも,φ(2k)=2k-2k-1=2k-1 は偶数

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

 

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

 

そこで,m=st,s>2,t>2,(s,t)=1で,mが奇数でも 偶数でもφ(s),

φ(t)は共に偶数であり,もちろん, φ(m)=φ(s(t)=φ(s)φ(t)も

偶数です。

 

それ故,φ(m)/2,φ(s)/2,φ(t)/2は全て整数です。

 

しかも,(a,m)=1なる任意の整数aに対して,

φ(m)/2=φ(s)φ(t)/2なので,Eulerの定理から

φ(m)/2=(aφ(s))φ(t)/2≡1 (mod s),かつ,

φ(m)/2=(aφ(t))φ(s)/2φ(m)/2≡1 (mod m) を意味します。

 

φ(m)>0なので,明らかにφ(m)/2<φ(m)ですから (a,m)=1

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

 

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

 

また,pが奇素数,nが自然数でm=pnと書ける場合には,

あるmの原始根a=gが常に存在することは既にわかっています。

 

さらに,そのとき偶数のm=2pnの形のmについても,そのgか,

または,(g+pn)のいずれがmの原始根となるきとが既に示されて

います。

 

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

m=2,4,および,pを奇素数,nを自然数としてm=pn,または

m=2pn 2と書ける場合に限られることが示されました。

(証明終わり

 

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

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

|

« 原始根と指数(2) | トップページ | 無為徒食(畜生(ちくしょう))。。普通の日記 »

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

コメント

コメントを書く



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




トラックバック


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

« 原始根と指数(2) | トップページ | 無為徒食(畜生(ちくしょう))。。普通の日記 »