303. 代数学・数論

2019年1月16日 (水)

記事リバイバル⑩(リーマン予想と素数定理)

※前記事に続く同じテーマの2007年8/11の過去記事

「リーマン予想と素数定理」を再掲載します。 ※

素数定理:π(x) ~ x/logx は,現在も未解決のリーマン予想

=R.H(Riemann hypothesis)の解決を待つまでもなく,既に証明

されていますが,Riemann予想が元々は精密な素数定理を導くこと

を,その目的としていたことはよく知られています。

 

しかし,ゼータ関数(Zeta)の零点が素数の個数分布π(x)と

具体的に,どのように結びつくのか?の詳細については私は

知らなかったので,ちょっと調べてみました。

 

本ブログでは,2006年10/30に「ベルヌーイ数とゼータ関数」,

10/31には,その続編「ベルヌーイ数とゼータ関数(その2)

という記事を書きました。

 

そこでは,整数のべき乗数列の有限和のBernoulli(ベルヌーイ)数

による表現として,Euler-Maclaulinの和公式を与えました。

 

すなわち,s≠1なら,

n=1N(1/ns)=(1-1/Ns-1)/(s-1)+(1/2)(1+1/Ns)

+∑k=1M-1[Bk+1/(k+1)!](s)k(1-1/Ns+k)

-{(s)M/M!}1NM(x-[x])x-s-Mdx

なる公式です。

 

ただし,Mは任意の自然数,BrはBernoulli数,であり,記号:

(s)kは,(s)k≡s(s+1)...(s+k-1)で定義されます。

 

そして,Riemannのゼータ関数:ζ(s)は,Re(s)>1の複素数s

対して,ζ(s)≡∑n=1(1/ns)で定義されるのですが,上の

Euler-Maclaulinの和公式の右辺は,この範囲では絶対収束します。

 

そこで,両辺のN→ ∞ の極限を取ると,

ζ(s)=∑n=1(1/ns)

=1/(s-1)+1/2+∑1M-1[Bk+1/(k+1)!](s)k

-{(s)M/M!}1M(x-[x])x-s-Mdx;(Re(s)>1)

という表現式が得られます。

 

ところが,右辺の積分式の方は,

Re(s)>(1-M)の範囲で絶対収束するので,この式の右辺に

よって,ゼータ関数ζ(s)は,Re(s)>(1-M)の範囲のsに

自然に解析接続されます。

 

Mは任意の自然数ですから,ζ(s)はs=1に"特異点=1位の極"

を持つだけで,この点を除く全複素s平面に解析接続されます。

 

そこで,今日はまずRiemannの原論文に従ってsと1-sの交換

対して不変な関数:π-s/2Γ(s/2)ζ(s)を考察することから

始めます。

 

まず,EulerのΓ関数の定義Γ(s)≡∫0s-1exp(-x)dxに

部分積分を繰り返すことによって,等式:

Γ(s)/ns=∫0s-1exp(-nx)dx

が得られます。

 

これから,Γ(s)ζ(s)=∫0[xs-1/{exp(x)-1}]dx

が成立することがわかります。

 

故に,積分:∫0[(-x)s-1/{exp(x)-1}]dxの積分路が囲む

1位の極;x=±2πniの留数の寄与を考えると,

 

2sin(πs)Γ(s)ζ(s)=(2π)sΣ1s-1[is-1+(-i)s-1]

=(2π)sζ(1-s)2sin(πs/2) を得ます。

 

公式:Γ(s)Γ(1-s)=π/sin(πs)より,

sin(πs)=π/[Γ(s)Γ(1-s)],

sin(πs/2)=π/[Γ(s/2)Γ(1-s/2)]ですから,

 

ζ(s)/Γ(1-s)=(2π)sζ(1-s)/[Γ(s/2)Γ(1-s/2)]

となります。

 

一方,Legendreの関係式:Γ(s)=2s-1π-1/2Γ(s/2)Γ((s+1)/2)

より,Γ(1-s)=2-sπ-1/2Γ((1-s)/2)Γ(1-s/2) です。

 

結局,関数等式:π-s/2Γ(s/2)ζ(s)

=π-(1-s)/2Γ((1-s)/2)ζ(1-s) が得られます。

 

よって,確かにπ-s/2Γ(s/2)ζ(s)は,sと(1-s)の交換に

ついて対称であることがわかりました。

 

 さて,Γ(s)/ns=∫0s-1 exp(-nx)dxと同様に,

 部分積分により,

 π-s/2Γ(s/2)/ns=∫0s/2-1exp(-n2πx)dx

 が得られます。

 

 そこで,関数ψを関数:ψ(x)≡Σn=1exp(-n2πx)

 (↑ 今日では,Jacobiのテータ関数と呼ばれている)

 によって定義すれば,

 

 π-s/2Γ(s/2)ζ(s)=∫0s/2-1ψ(x)dx

 となります。

 

 ここでψ(x)の既知の性質:2ψ(x)+1=x-1/2{2ψ(1/x)+1}

 を用いると,

 

 π-s/2Γ(s/2)ζ(s)

 =1s/2-1ψ(x)dx+∫01(s-3)/2ψ(1/x)dx

 +(1/2)∫01(x(s-3)/2-xs/2-1)dx

 =1/{s(s-1)}+∫1(xs/2-1+x-(1+s)/2)ψ(x)dx

 となります。

 

そして,これの右辺第2項の積分は全てのsについて正則なので

結局,π-s/2Γ(s/2)ζ(s)は,s=0,1の1位の極を除いて全s

平面で正則であることがわかります。

 

一方,ガンマ関数の性質から,Γ(s/2)はs=-2,-4,..に1位の極

を持つことが知られていますが,

 

π-s/2Γ(s/2)ζ(s)は,それらのsでは正則で,しかもゼロでは

ないので,ζ(s)がs=-2,-4,..に重複度1の零点を持つこと

がわかります。

 

これをζ(s)の自明な零点といいます。

 

先に述べたEuler-Maclaullinの和公式でも,mを自然数とするとき,

ζ(1-m)

=-1/m+1/2+∑1m-1[Bk+1/(k+1)!](1-m)(2-m)..(k-m)

と書けることから,

 

m=3,5,..ではζ(1-m)=-Bm/m=0

となることがわかります。

 

しかも,ζ(1-m)/(1-m)≠0 ですから,これら自明な零点は

重複度が1であることがわかります。

 

いずれにしても,ζ(s)の自明な零点はΓ(s/2)の極によって

相殺されます。

 

そして,Γ(s/2)は零点を持ちませんから,π-s/2Γ(s/2)ζ(s)

の全ての零点は,ζ(s)の自明でない全ての零点と完全に一致

します。

 

2006年10/24の記事:「素数を分母とする循環小数とその周辺」,

および,10/25の記事;「素数定理への入り口」において,

 

Eulerによるゼータ関数:ζ(s)の素数pによる無限積表示

(=Euler積):ζ(s)=Πp=素数(1-p-s)-1を紹介して,

これによってlog{ζ(s)}=-Σlog(1-p-s)が成立すること

を既に記述しています。

 

そして,s=σ+iτ(σ,τ:実数)とおけば,|p-s|=pであり,

σ>1 のときは,

-Σlog(1-|p-s|)=-Σlog(1-p)≦Σp<∞

です。

 

つまり,

σ=Res>1なら,log{ζ(s)}=-Σlog(1-p-s)は有限なので,

Res>1 には,"ζ(s)の零点=π-s/2Γ(s/2)ζ(s)の零点"は

存在しないことがわかります。

 

また,関数等式:π-s/2Γ(s/2)ζ(s)

=π-(1-s)/2Γ((1-s)/2)ζ(1-s)

による,sと(1-s)の交換対称性から,Re(1-s)>1,

はRes<0 と同値ですから,

 

結局,Res<0 にもRes>1にも,π-s/2Γ(s/2)ζ(s)の零点

は存在しないことがわかります。

 

つまり,"π-s/2Γ(s/2)ζ(s)の零点=ζ(s)の自明でない零点"

は,存在すれば,0≦Res≦1の領域にしかないことになります。

 

ここで唐突ですが,複素関数論で現われる正則関数の零点に関する

Weierstrassの標準形を考えます。

 

これは,正則関数f(z)が重複度も含めてn個の零点:

1,a2,..,anを持てば,

f(z)の一般形は,g(z)を整関数として,

f(z)=exp{g(z)}(z-a1)(z-a2)...(z-an)

なる形に書けること,を意味します。

 

しかし,このままではn→ ∞ に移行するときに不便なので,

これをak≠0 なる全ての零点について,(-ak)で割ります。

 

mをak=0 なる零点の重複度とすると,Σn|1/an|<∞ ならば,

n→ ∞ では,f(z)=zmexp{g(z)}Πan≠0(1-z/an)という

形に書けるという定理が成立します。

 

しかし,一般にはΣn|1/an|<∞ が成立するとは限りません。

そこで,より一般的な展開式は,mn∀t>0 に対して,

Σn{2/(mn+1)}|t/an|mn+1<∞ なる最小の正の整数とすると、

 

f(z)=zmexp{g(z)}Πan≠0[(1-z/an)

exp{(z/an)+(z/an)2/2+...+(z/an)mn/mn}]

と書けるという式になります。

 

これが"Weierstrassの標準形"です。

  

特に,z= 0 がf(z)の零点ではなく,

Σn|1/an|=∞,Σn|1/an|2<∞ の場合には,

f(z)=Cexp(Bz)Πan≠0[(1-z/an)exp(z/an)]

と表わすことができます。

 

ここでは「Weierstrassの因数分解定理と有理型関数」という

murakさんのホームページのpdf情報を参照しました。

 

これによると,s(1-s)π-s/2Γ(s/2)ζ(s)は,s平面で正則

で,その零点=ζ(s)の自明でない零点ρ,は全て単根でρ≠0

であり,Σρ|1/ρ|=∞,Σn|1/ρ|2<∞なので,

 

s(1-s)π-s/2Γ(s/2)ζ(s)

=Cexp(Bs)Πρ[(1-s/ρ)exp(s/ρ)]

と表現できます。

 

この両辺でs→ 0 とすると,sΓ(s/2)ζ(s)→ 2ζ(0)=-1

なのでC=-1 です。

 

また,s→ 1 とすると,(1-s)π-s/2Γ(s/2)ζ(s)→ -1

なので,1=exp(B)(1-1/ρ)exp(1/ρ) です。

 

さらに,exp(Bs)Πρ[(1-s/ρ)exp(s/ρ)]の,s→ (1-s)

に対する不変性により,

exp(B)=Πρ[{(1-ρ)/(-ρ)]exp{-1/(1-ρ)}]

と書けます。

 

結局,s(1-s)π-s/2Γ(s/2)ζ(s)=-Πρ(1-s/ρ)

が得られました。

 

右辺最後の式:Πρ:零点(1-s/ρ)は,Hadamad(アダマール)積

といいます。

 

したがって,ζ(s)=Πp.素数(1-p-s)-1

=[-π-s/2Γ(s/2)/{s(1-s)}]Πρ:零点(1-s/ρ)

という関係式が得られます。

 

Euler積とHadamad積の間には,こうした美しい関係があることが

わかりました。

 

これは素数とゼータの零点の間に成り立つ1つの双対性(Duality)

であると考えられます。

 

Euler積表現:ζ(s)=Πp.素数(1-p-s)-1の両辺をsで対数微分

すると,log(ζ(s))/ds=Σp.素数(1-p-s)-1logp

=Σn=1Λ(n)n-sと表わすことができます。

 

ここで,Λ(n)はvon Mangoldtの関数と呼ばれるnの関数で,

Λ(n)≡logp(n=pm:m≧1のとき),Λ(n)≡0 (それ以外)

です。

Hadamad積表現:ζ(s)

=[-π-s/2Γ(s/2)/{s(1-s)}]Πρ:零点(1-s/ρ)も,

sで対数微分して,Euler積表現の式に等置すれば,

dlog(ζ(s))/ds=Σn=1Λ(n)n-s

=1/s+1/(s-1)-1/2logπ+Γ'(s/2)/{2Γ(s/2)}

-Σρ:零点{1/(s-ρ)}

なる式を得ます。

 

ここで,前に戻り,ζ(s)においてs=1/2+it,または,

t=i(1/2-s)(tは複素数)とおいて,

ξ(t)≡π-s/2Γ(s/2+1)(s-1)ζ(s)

={s(s-1)/2}π-s/2Γ(s/2)ζ(s)と書けば,

 

ξ(t)=1/2-(t2+1/4)∫1dx[x-3/4cos{(tlogx)/2}ψ(x)],

または,

ξ(t)=4∫1dx[x-1/4cos{(tlogx)/2}d{x3/2ψ(x)}/dx]

と書けます。

 

これから,ξ(t)はtの偶関数であり,しかもtが実数ならξ(t)

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

 

このとき,ξ(t)=0 となる根tで 0≦Ret≦Tなるものの個数:

すなわち 0≦Res≦1(-1/2≦Imt≦1/2),かつ,

0≦Ims≦T(0≦Ret≦T)を満たすζ(s)の自明でない零点;

ρ=sの個数をN(T)と書けば,

"N(T)={T/(2π)}log{T/(2π)}-{T/(2π)}+o(logT)

である。"という命題が成立することに関する,Riemannの幾分

不十分な説明が与えられていますが,

これは1905年に von Mangoldt によって,厳密な証明が与えら

れています。

 

そしてξ(α)=0 を満たす任意の根をαとします。

 

ρ=1/2+iαですからα=i(1/2-ρ)ですが.このときRiemann

によれば,上に求めた,

N(T)={T/(2π)}log{T/(2π)}-{T/(2π)}+o(logT)

という表式を考慮することで,

積公式:ξ(t)=ξ(0)ΠReα>0(1-t22):つまり,

logξ(t)=ΣReα>0log(1-t22)+logξ(0)が得られるという

ことです。

 

これも,Riemannの説明は私にははっきり言ってよく理解できません。

 

実際これも不十分な説明で,厳密な証明はHadamardによって,1896年

に与えられたらしいです。

 

しかし,むしろ先に求めた等式;

log(ζ(s))/ds=Σn=1Λ(n)n-s

=1/s+1/(s-1)-1/2logπ+Γ'(s/2)/{2Γ(s/2)}

-Σρ:零点{1/(s-ρ)}と,

 

ξ(t)={s(s-1)/2}π-s/2Γ(s/2)ζ(s)という表式,

および,ξ(t)の偶関数性から,

dlog(ξ(t))/dt=iΣρ{1/(s-ρ)}

=ΣReα>0{1/(t-α)+1/1/(t+α)} を得ます。

 

この両辺を,0からtまで定積分すると,

log(ξ(t))-log(ξ(0))=ΣReα>0[log(t±α)-log(±α)]

=ΣReα>0log(1-t22) が,直接得られるので,

先のRiemannの説明は不要ですね。

 

そして,このξ(t)の表式をζ(s)の表式に翻訳すると,

log(ζ(s))=(s/2)logπ-log(s-1)-log{Γ(s/2+1)}

+ΣReα>0log{1+(s-1/2)22}+log(ξ(0))

なる式が得られます。

 

次に任意の正の実数xより小さい素数の個数を,慣例によって,

π(x)で表わし,xの関数F(x)を,

xが素数でないならF(x)≡π(x),

xが素数ならF(x)≡limε→0[π(x+ε)+π(x-ε)]/2

=π(x-0)+1/2

によって定義します。

 

さらに,関数f(x)を

f(x)≡F(x)+F(x1/2)/2+F(x1/3)/3+...

=Σm=1[F(x1/m)/m]

で定義します。

 

log(ζ(s))=-Σplog(1-p-s)

=Σp-s+Σp-2s/2+Σp-3s/3+...

=Σm=1p-ms/m]であり,-ms=s∫pm-s-1dxなので

log(ζ(s))/s=∫1-s-1f(x)dx

が得られます。

 

そして,Fourierの反転公式によれば,

f(x)={1/(2πi)}∫a-i∞a+i∞ds[xslog(ζ(s))/s]

です。

 

ただし,右辺が収束しない場合を考慮して,1回引き算した形

にすると,f(x)=[{1/(2πi)}/logx]∫a-i∞a+i∞ds

[xsd{log(ζ(s))/s]/ds] となります。

 

これに,log(ζ(s))

=(s/2)logπ-log(s-1)-log{Γ(s/2+1)}

+ΣReα>0log{1+(s-1/2)22}+log(ξ(0))

を代入します。

 

例えば,

-log{Γ(s/2+1)}

=limm→∞Σn=1n-mlog{1+s/(2n)}-(s/2)logm}ですから,

d[log{Γ(s/2+1)}/s]/ds

=Σn=1(d[log{1+s/(2n)}/s]/ds)

です。

 

よって,log(ξ(0))を別にすれば,f(x)を示す右辺の積分の全て

の項が,

[{±1/(2πi)}/logx]

a-i∞a+i∞ds[xsd{log(1-s/β)/s}/ds]

という形をしています。

 

{log(1-s/β)/s]/dβ=1/{β(β-s)}ですから,

{1/(2πi)}∫a-i∞a+i∞ds[xsd{log(1-s/β)/s]/dβ]

なる積分を計算すると,

 

{1/(2πi)}∫a-i∞a+i∞ds[xs/{β(β-s)}]=xβ

です。

 

そして,これはResが Reβより大きいとき,Reβが負であるか?

正であるか?によって,

 

β/β=∫xβ-1dx=(d/dβ)∫x[xβ-1/logx]β-1dx,

または,

β/β=∫0xβ-1dx=(d/dβ)∫0x[xβ-1/logx]β-1dx

となります。

 

それ故,

[{1/(2πi)}/logx]∫a-i∞a+i∞ds[xsd{log(1-s/β)/s}/ds]

=∫x[xβ-1/logx]dx+(定数),または,

0x[xβ-1/logx]dx+(定数)です。

 

具体的には,

[{1/(2πi)}/logx]∫a-i∞a+i∞ds

(xsd[log{Γ(s/2+1)}/s]/ds)

=∫x[1/{x(x2-1)logx}]dx,

 

[{1/(2πi)}/logx]∫a-i∞a+i∞ds

[xsd{log(s-1)/s}/ds]=Li(x)

を得ます。

 

ただし,Li(x)は対数積分と呼ばれる関数で,

Li(x)≡∫0x(du/logu)

=limε→0[∫01-ε(du/logu)+∫1+εx(du/logu)]

で定義されます。

 

そして,f(x)

=[{1/(2πi)}/logx]∫a-i∞a+i∞ds[xsd{log(ζ(s))/s]/ds]

=Li(x)―Σα[Li(x1/2+αi)+Li(x1/2-αi)]

+∫x[1/{x(x2-1)logx}]dx-log2

となることがわかります。

 

これは,「Riemannの素数式」と呼ばれます。

 

一方,f(x)=Σm=1[F(x1/m)/m]の反転公式は,

F(x)=π(x)=Σm=1[μ(m)f(x1/m)/m]

で与えられます。

 

ここで,μ(m)は,数論でよく知られたMobius関数で,

μ(m)≡(-1)(mの素因数分解:m=p12...pk;k個の

素数p1,p2,...,pkが全て相異なる素数のとき),

μ(m)≡1(m=1のとき),μ(m)≡0 (それ以外のとき)で

定義されるものです。

 

結局,F(x)=π(x)=Σm=1[μ(m)f(x1/m)/m],

f(x)=Li(x)―Σα[Li(x1/2+αi)+Li(x1/2-αi)]

+∫x[1/{x(x2-1)logx}]dx-log2 なる式が,

素数定理の表現を与えることがわかりました。

 

素数定理:π(x)~ Li(x)はRiemann予想とは別に,

1896年にHadamardや,de la Vallee-Poussinによって

証明されましたが,

 

π(x)~ Σm=1[μ(m)Li(x1/m)/m]という近似式の方が

より優れていることが,かなり大きいxまで検証されています。

 

ここまでは,ζ(s)の自明でない零点が全て 0≦Res≦1 の領域

にあれば成立することであり,特にRiemann予想が成立することを

必要としません。

 

しかし,特に,

"ζ(s)の自明でない零点が全てRes=1/2の上にある。"

というRiemann予想が成立するなら,

 

素数定理"π(x) ~ Li(x)"はより精密に,Riemann予想と同値な

命題であることが,1901年にvon Kochによって証明されている定理

として,

 

"F(x)=π(x)=Li(x)+o(x1/2+ε) (εは任意の正の数)"

に置き換わることになります。

 

最後に挙げた命題が,Riemasnn予想と同値な命題であることの

理由については,まだ把握していませんが,もしも詳細が理解

できたなら,そのときにはまた紹介したいと思います。

 

参考文献:鹿野 腱 編著「リーマン予想」(日本評論社);

梅田 亨,黒川信重,若山正人,中島さち子 著

「ゼータの世界」(日本評論社),

 

荒川恒男,伊吹山知義,金子昌信 著

「ベルヌーイ数とゼータ関数」(牧野書店) ;

E.Artin著(上野建爾 訳・解説)

「ガンマ関数入門」(日本評論社)


 

| | コメント (0) | トラックバック (0)

2019年1月15日 (火)

記事リバイバル⑨(素数定理とその周辺)

※リバイバル記事の第九弾は数論の素数定理関連からです。

まず,,2006年10/24の「素数を分母とする循環小数とその周辺」を再掲載※

 今日は素数を分母とする循環小数の周辺の話題について書いてみます。 

 10と互いに素な素数,2と5を除く素数pを分母とする分数 1/pを, 

 1/p = 0.1..am1..am12..am..なる循環小数で表わすと,

 

 (10m/p)-1/p=(1/p)(10m-1)=(10m-1)/p

 =10m-1110m-22+..m=(自然数) なる式が成立します。

 

 そこで,1/pの循環節の長さは(10m-1)をpで割ったときに割り切れるような自然数mの最小値であるということができます。

 例えば,分数1/7(素数pが7の1/p)を考えたときには,106-1

=999999を7で割ると割り切れて商は142857です。

 

 一方,1/7を小数で表現すると,1/7=0.142857142857142857.

となりますから,循環節の長さは確かに6=p-1です。
 

 「フェルマーの小定理」から,素数pに対しては10p-1≡1(mod p) 

が成立するので,(10m-1)をpで割ったときに割り切れる 

最小の自然数mは必ず(p-1)の約数です。
 

 というわけで循環節の長さが最大となるのはm=p-1のときです。

 

※ 2006年9/12の記事

オイラーの定理とフェルマーの小定理(合同式)」,

続く9/13の記事「フェルマーの小定理の別証明

も参照してください。 ※

 では,mが丁度,最大値(p-1)になるのはどういう場合でしょうか?

 

 それは,k=1,2,..,(p-2)に対しては決して10k≡1(mod p)

とならないときですから,pが10を原始根とする場合です。

 

 体:(Z/pZ)からゼロと合同な元を除いた既約剰余類のつくる

巡回群=(Z/pZ)×を剰余類rの巡回群として

<r>={1,r,r2,r3,..,rp-2}={1,2,..,p-1}と書くことが

できるとき,rとして取り得る値。。というのがpの原始根の定義

です。 

 そして,pが10を原始根とする場合に限って,1/pの循環節

の長さが最大の(p-1)になります。

 例えば,p=7のとき10,102,103,104,105,106は7を法として,

それぞれ3,2,6,4,5,1となりますから,この場合は10は原始根で

あり確かにp-1=6が循環節の長さです。

 Gauss(ガウス)によれば,10を原始根とする100までの素数は.7,17,19,23,29,47,59,61,97の9個だそうですから,例えば

1/47は循環小数で小数点以下46桁までを繰り返すということ

になりますね。

 実数x以下の自然数で10を原始根とする素数pの個数を

π10(x)とし,x以下の素数全体の個数をπ(x)とします。

 

 それらのx→ ∞での比をCとすると,

10(x)/π(x)] → Cですが,E.Artin(アルチン)によると,

C=Π[1-1/p(p-1)]~ 0.37395 だそうです。

 Artinのこの予想が正しいとすると,素数定理;

 π(x)~ (x/logx)(x→ ∞)を用いることで,

 π10(x)~ C(x/logx) と書けることになります。

 ところで,Eulerによるゼータ関数:ζ(s)の素数pによる

 無限積表示:ζ(s)=Π(1-1/ps)-1で,s=1とおけば,

 Π(1-1/p)-1=∑(1/n) です。

 

 そして,∑1n[1/(k+1)]<∫1n(1/x)dx<∑1n(1/k)より,

 0<[∑1n(1/k)-logn]<1 です。

 

 これから,n→∞に対して1n(1/k)-logn→γ (0<γ<1)です。

 

 そこで,x→∞に対して∑1x(1/n)~ logx が成立します。

 ただし,γはオイラー数(Euler number)です。

 

 したがって,Eulerの無限積表示:Π(1-1/p)-1=∑(1/n)は,

 [-∑log(1-1/p)]~ log(logx) なることを意味します。

 

 ところが,log(1-x)~ -xですから,これは

 ∑(1/p)~ log(logx)であることを示唆していて,素数定理

 への入り口を与えるものでしょう。

 素数定理π(x)~ (x/logx)の証明には,実は,

 

"ζ(s) の自明でない零点は全てRe(s)=1/2 の上にある。"

というリーマン予想(Riemann's hypothesis)までは必要なく,

 

 "ζ(s)が Re(s)≧1では零にならない。"という性質だけで

十分です。

 

 これを用いてHadamard(アダマール)らによって,素数定理は既に

証明されています。

 しかし,リ-マンはリーマン予想を解決することで,もっと

 複雑な素数公式を得ることを目指していたらしいですね。

 

 参考文献;黒川信重 他 著「ゼータの世界」(日本評論社)

※この続きで2006年10/25の「素数定理への入り口」も再掲します。※

"実数x以下の素数全体の個数をπ(x)とすると,x→ ∞では

π(x)~(x/logx)となる。"という素数定理に関する部分は

時間がなくて尻切れトンボになってしまいました。

Eulerによるゼータ関数ζ(s)の素数pによる無限積表示:

ζ(s)=Π(1-1/ps)-1でs=1とおけば,Π(1-1/p)-1=∑(1/n)

と書けます。 

 

[∑1n(1/n)-logn]→γ (n→ ∞)

(ただしγはEuler数で 0<γ<1)ですから,

1x(1/n)~logx (x→ ∞)です。 

 

したがって,[-∑log(1-1/p)]~ log(logx)です。 

 

ところが,log(1-x)~ -xですから,上式は

(1/p)~log(logx)なることを示唆しており,これは

素数定理への入り口を与えるものでしょう。 

 

ここでの∑はp≦xのあらゆる素数にわたる総和です。

と書きましたが,どうしてこれが素数定理への入り口に

なるのか?

 

の明確な意味を述べていませんでした。

※昨晩から今朝までの夜勤の合間の休憩時間にちょっと計算し,

これは次のような意味であろうと自ら推測しました。※

 p~x付近でのπ(x)の変化をΔπとすると,その付近での

∑(1/p)の変化はΔ[∑(1/p)]~(1/x)Δπと近似できるため,

 ∑(1/p)~log(logx)から,(1/x)Δπ~Δlog(logx)

 =[Δlogx]/logx=Δx/(xlogx)です。

 

 すなわちΔπ~Δx/logxと考えられます。
 したがってπ(x)~∫dx(1/logx)であると予想されるわけです。

 素数定理としては,このままの式でもいいのでしょうが,xが

大きいときは分母のlogxは大体xの桁数を表わすだけなので,

これはxに対してほとんど変動がないのと同じです。 

 

 結局,π(x)~(x/logx)であるとしても,同じ意味

 と思われます。

| | コメント (0) | トラックバック (0)

2015年2月24日 (火)

連分数と近似分数(3)

 連分数と近似分数に関する記事の続きです。

 この項目はこれで最後です。

 前回最後では,まず,「2次の無理数ωの連分数展開が初項から

 直ちに循環が始まる純循環連お分数になるための必要十分条件は

 ω>1かつ,-1<ω<0 が成立することである。」という

 純循環連分数に対するGalois(ガロア)の定理を証明し,

 

その応用として,

「2以上の正の整数で平方数でない数dの平方根√dの

連分数展開√d=[k0,k1,k2,..]は,初項のすぐ次の第1項

ら純循環連分数である。」

という謂わゆるLagrange(ラグランジュ)の定理を証明しました。

 

今回の記事では,まず,実際にいくつかの平方数でない素数dに

ついて平方根√dの循環連分数展開表現を与えて,これにより

具体的な無理数である√dの近似分数を計算してみます。

 

まず,√3,については,既に√3=[1,1,2]なることをを示しました。

 

そこで,既に示した手法による√3の近似分数列の最初の5つ

は,α01,α1=[1.1]=1+1=2,α2=[1.1,2]=1+1/(1+1/2)

=5/3=1.666..,α3[1.1,2,1]=1+1/[1+1/{2+1}]]

=7/4=1.75,α4[1.1,2,1,2]=1+1/[1+1/{2+1/(1+1/2)}

=19/11=1.72727.., となります。

 

これ以上の近似は,計算が面倒なので上で得られた公式に従って

行ないます。

 

すなわちn=pn/qnとn次近似の既約分数を表わすと,

n=pn-1n+p-n-2,n =qn-1n+qn-2 です。

 

この公式から5=[1,1,2,1,2,1]=p5/q5,

において,p5=p45++p3,5 =q45+q3より,

5=19×1+7=26,q5 =11×1+4=15なので, 

α526/15=1.73..,です。

 

同様に6=(26×2+19)/(15×2+11)=71/41=1.731707317..

となります。

 

冒頭で述べたように,分母が100よりも小さいにも関わらず,

分数173/100よりも3の真の値との近似誤差が小さい√3の近似

分数:71/41が得られました。

 

また,√2については,ω=√2-1と置くと,(1+ω)2=2より, 

ω(ω+2)=1です。

 

故に, ω=√2-1は,ω=1/(2+ω)=1/{2+1/(2+ω)}

=1/[2+1/{2+1/(2+ω)}]=..=[2]となって,長さが1の

純循環連分数[2]で表現されます。

 

したがって,√2は,√2=[1,2]と表わされます。

 

そこで,√2の,近似分数列は,

α0=1,α1=[1.2]=1+1/2=3/2=1.5, 

α2[1.2,2]=1+1/(2+1/2)=7/5=1.4, 

α3[1.2,2,2]=1+1/[2+1/{2+1/2}]]=17/12=1.41666..,

と続きます。

 

以下4=[1.2,2,2,2]=(17×2+7)/(12×2+5)=41/29

=1.413793103..,α5[1.2,2,2,2,2]=(41×2+17)/(29×2+12)

=99/70=1.414285714... です。

 

しかしながら,実際にω=√2-1=[2]という風に循環連分数として

明確に表現することができないなら,いくら連分数からっ分数への

近似法がわかっていても,絵に書いたモチのようなものです。

 

例えば,元の講談社ブルーバックスのタネ本には√23=[4,1,3,1,8]

という例が書いてありました。

 

このタネ本の中では,上述のLagrangeの定理の応用として,

0=[√23]=4 から,ω=4+√23,および,ω=4-√23が

Galoisの定理の純循環連分数の条件を満たし,

ω=4+√23=[8,1,1,3]と書けるということから,

√23=[4,1,3,1,8]を導出していましたが,これ以上は具体的

な記述がありませんでした。

 

そして,入院中の私にはいくらトライしても

ω=4+√23=[8,1,1,3]も,√23=[4,1,1,3,8]も自力で導く

ことができず,そのときはあきらめて挫折しました。

 

この√23の値は,てっとり早く電卓で調べてみると,

√23=4.795831523..です。

 

取り敢えず,√23=[4,1,3,1,8]という表現を信用して近似分数列

を計算すれば,

まず0=4,α1=[4.1]=5,

α2=[4,1,3]=4+1/(1+1/3)=19/4=4.75, 

α3[4,1,3,1]=4+1/[1+1/(3+1)]]=24/5=4.8..

となります。

 

以下,公式を用いてさらに続けると, 

α4[4,1.3,1,8]=(24×8+19)/(5×8+4)

=211/44=4.795454545.., 

α5[4,1.3,1,8,1]=(2111×1+24)/(44×1+5)

=235/49=4.7918367..と連分数による近似分数列

が得られます。

 

これらは確かに真の値の両側から挟むように

23=4.795831523..に収束していっていると見えます。

 

しかし,もしも√23=[4,1,3,1,8]の右辺のような循環連分数

展開の表現を正しく得る方法が不明なら,こうした精緻な近似

分数を得ることはできません。

 

私は,入院中には,√3や√2の連分数展開を求めた場合と同様に, 

23ついてもω=√23-4と置いて,

(ω+4)2=23からω(ω+8)=7より,ω=7/(ω+8)なる式から

出発して,右辺を分子が1の連分数に変形する方法にこだわって

ずっと考えていました。

 

しかし,結局,√23については挫折したので,上記の√3や√2に

ついて連分数を求めた方法は,必ずしも全ての√dの展開にも

当てはまるような系統だった方法ではなく,別の方法を見つける

必要があるのでは?と思うに至りさらに考えて見ましたが,

そのときは,自由に動けなくて適切な参考書もなく,あきらめて

別のことに興味が移行したのでした。

 

退院してからは,それ以上の努力を怠って,安易な他力本願の道

に入り,連分数について書かれたいくつかの文献をネット検索

してみました。

 

結局,詫間項等工業専門学校の橋本竜太氏のPDF

実数の有理数近似と連分数展開 

に適切な手法が書かれているのを見つけて,それをマネて

計算しました。

 

すなわち,まず,ω=4+√23に対して,まず,k0=[ω]=8です。

 

ここで,ω=[k0,k1,k2,..km,0,k1,..]=[0,k1,k2,..km]

なら,これは,ω=k0+1/[k1+1/{k2+1/(k3+..,を意味します。

 

そこで,k0=[ω]=8に対し,ω1=1/(ω-k0)=1/(√23-4)

=(√23+4)/7と置けば,

ω=k0+1/[k1+1/{k2+1/(k3+..,によって, 

1[1/(ω-k0)]=[ω1]となるはずですから,

1=1を得ます。

 

以下,同様に,ω2=1/(ω1-k1)=7/(√23-3)=(√23+3)/2

より,22]=3です。

そして,ω3=1/(ω2-k2)=2/(√23-3)=(√23+3)/7 

より,k3=[ω2]=1です。

 

さらに4=1/(ω3-k3)=7/(√23-4)=(√23+4)より, 

44]=8ですが,ここでω4がω=4+√23に一致するため 

以下のkjは循環することがわかります。

 

すなわち,ω=4+√23=[8,1,3,1,8,1,..]となって確かに

純循環連分数となり,ω=4+√23=[0,k1,k2,k3]=[8,1,1,3]

であることがわかりました。

 

したがって,√23=ω-4=[4,1,3,1,8] が得られました。

 

試しに,参考書には載ってない√41の連分数展開にトライして

みました。

 

まず,ω=6+√41に対して,k0=[ω]=12 です。 

次に1=1/(ω-k0)=1/(√41-6)=(√41+6)/5より, 

11]=2です。

 

以下2=1/(ω1-k1)=5/(√41-4)=(√41+4)/5より,

2=[ω2]=2,ω31/(ω2-k2)=5/(√41-6)=(√41+6)

より,k3=[ω2]=12,

そして,ω41/(ω3-k3)=7/(√23-4)=(√23+4)より,

4=[ω4]=8です。

 

結局,ω=6+√41=[12,2,2]であり,√41=[6,2,2,12]と

なることがわかりました。

 

さて,電卓によれば,√41の値は√41=6.403124237ですが, 

連分数展開:√41=[12,2,2]による近似分数の列を構成すれば, 

α06,α1=[6.2]=6+1/2=6.5,α2=[6,2,2]=6+1/(2+1/2)

=32/5=6.4,α3[6,2,2,12]=6+1/[2+1/(2+1/12)]]

=397/62=6.403225806,

 

さらに漸化式の公式から4=[6,2.2,12,2]

=(397×2+32)/(62×2+5)826/129=,6.403100775..,,

および,α5[6,2.2,12,2,2]=(826×2+397)/(129×2+62)

=2049/320=6.403125を得ます。

 

確かに√41に収束する近似分数列になっているようです。

 

高校時代に語呂で覚えていたものくらいはエクササイズで全部

やってみました。

 

5=[2,4]={2,9/4,38/17,161/72.682/305,..}, 

6=[2,2,4]={2,5/2,22/9,49/20,218/89.485/198,..}, 

7=[2,1,1,1,4]

={2,3,5/2,8/3,37/14,45/17,82/31.373/141,..}, 

8=[2,1,4]={2,3,14/5,17/6,82/29,99/35,478/169,..}, 

10=[3,6]={3,19/6,117/37,721/228…} です。

 

ここで,改めて気付きました。 

8=[2,1,4]は,2√2=[1,2]の2倍の2√2に等しいいのですが,

連分数展開は線型演算ではないこともあり単純に

8=2√2=[2,4]ではないということです。

 

ただし,√2=1+1/[2+1/{2+1/(2+..ですから, 

8=2√2=2+2(1/[2+1/{2+1/(2+..)

=2+1//[1+1/2+1/(4+1/1+1/4+.より,

この場合は√8=[2,1,4]となることは簡単にわかります。

 

さて,最後に,ここまで追求してきた無理数の連分数展開に

よる近似値が,

「できるだけ分母が小さくて,しかもできるだけ真の値から

 の誤差が小さい分数(有理数)」という意味での最良近似値

を与えることを示します。

 

その内容は次の定理です。

 

[定理](最良近似)連分数展開による無理数ωの第n次近似分数 

αn=pn/qn (n≧1)はωの最良近似分数である。

 

すなわち,0<q≦qnを満たす任意の分数p/qに対して 

常に,|ω-(pn/qn)|≦|ω-(p/q)|が成立する。

 

特に等号はp=pn,かつ,q=qnのときのみである。

 

(証明)無理数ωが与えられ,それに対する連分数展開が既知

であり,近似分数列αn=pn/qn がわかっているとします。

 

このとき,任意の有理数a,bについての{aω+b}という形

の実数全体の集合は,係数a,bを有理数体,の元に限定する

と,ω,および,1の2つの元を一次独立な基底ベクトルとする

2次元の線型空間(ベクトル空間)を形成することは明らかです。

 

そして,この線型空間はωと1の代わりに,(qnω-pn-1)と

(qn-1ω-pn-1)を2つの基底とする有理数体の上の線型空間

とすることもできます。

 

それ故,今,0<q<≦qnを満たす任意の分数p/qを与える

整数p,qに対して(qω-p)を作ると,これを(qnω-pn)

と(qn-1ω-pn-1)の線型結合として,有理数係数A,Bにより,

qω-p=A(qnω-pn)+B(qn-1ω-pn-1)と表現すること

が常に可能です。

 

これから,(Aqn+Bqn-1-q)ω+(Apn+Bpn-1-p=0

ですから,q=Aqn+Bqn-1,p=Apn+Bpn-1 です。

 

これを,A,Bを未知数とする連立一次方程式と見てA,Bに

ついて解くと, 

A=-(pqn-1-qpn-1)/(pnn-1-qnn-1), 

B=-(pqn-qpn)/(pnn-1-qnn-1)ですが,

分母はnn-1-qnn-1(-1)n-1ですから,

 

A=(―1)n(pqn-1-qpn-1),B=(-1)n(pqn-qpn)

です。

 

もしもA=0 なら,pqn-1=qpn^1より,p/q=pn-1/qn-1=αn-1

であって,いずれも既約分数を仮定しているため,p=pn-1,q=qn-1

です。

 

一方,A≠0の場合,A>0,かつ,B>0とすると, 

A=(―1)n(pqn-1-qpn-1),B=(-1)n(pqn-qpn)は

共に整数なのでA≧1,かつ,B≧1です。

 

そこで,q=Aqn+Bqn-1より

q/qn=A+B(qn-1/qn-)>A≧1 なので, 

q>qn-1となり,0<q≦qnという仮定に矛盾します。

同様にA<0,かつ,B<0とすると, A≦-1,かつ,B≦-1

ですから/qn=A+B(qn-1/qn-)<A≦-1ですが,

そもそもqとqnは共に正整数ですから,こうなることは

ありません。

 

よって,AとBは互いに異符号です。

 

一方,以前に証明したように,近似分数列は1つおきに,一方は

ωより大きい方から他方はωより小さい方から,単調にωに収束

するため,隣り合った(ω-pn/qn)と(ω-pn-1/qn-1)も異符号

です。

 

n-1,qnは正整数ですから,これは(qn-1ω-pn-1)と(qnω-pn)

が互いに異符号であることを意味します。

 

したがって,結局,A(qnω-pn)とB(qn-1ω-pn-1)は同符号

ですから,|A(qn--pn)+B(qn-1ω-pn-11)| 

|A(qnω-pn)|+|B(qn-1ω-pn-1)| が成立します。

 

それ故,

|A(qnω-pn)+B(qn-1ω-pn-1)|≧|A|qnω-pn|

であり,等号はB(qn-1ω-pn-1)|=0 のとき,

まり,B=(-1)n(pqn-qpn)=0 のとき,

p=pn,かつ,q=qnのときのみであるのは明らかです。

 

 不等式:|A(qnω-pn)+B(qn-1ω-pn-1)|≧|A|qnω-pn|

 において,Aは整数ですから,|A|≧1より, 

 |A(qnω-pn)+B(qn-1ω-pn-1)|≧|qnω-pn|

 です。

 

 ここで,qω-p=A(qn-1ω-pn-1)+B(qnω-pn) 

 であったことから,|qω-p|≧|qnω-pn|と結論されます。

 

 両辺をq>0で割ると,|ω-(p/q)|≧|qnω-pn|/q

ですが,さらに,0<q≦qnより,(q/qn)≧1 ですから, 

 |qnω-pn|/q≧|ω-(pn/qn)|です。

 

 以上から,|ω-(p/q)|≧|ω-(pn/qn)|が成立し,

 αn=pn/qnこの大きさの分母でのωとの誤差最小

の近似値であることが証明されました。  (証明終わり)

 

これで,連分数を用いて無理数の近似分数を求めるという

テーマの記事を終わります。

| | コメント (1) | トラックバック (0)

2015年2月19日 (木)

連分数と近似分数(2)

前置きなしで連分数の続きです。

記事草稿は前回のアップのときにできていて,ただ長くなり過ぎたので分割しただけですがバタバタと忙しくて間が開きました。

年金など小金が入ると,つい昔の買い物中毒のムシが騒いだり

します。

連分数については,この記事をアップしても,なお,連分数に

よる近似分数が無理数の最良近似であるということを証明

するというタスクが残っていますが。。。

 

さて,具体的な例で個々の連分数から通分を繰り返して近似分数

を作るのは進めば進むほど厄介な作業になるので,便利な公式が

ないか調べてみます。

 

改めて,無理数ωの無限連分数展開をω=[k0,k1,k2,..]とする

とき,このωのj番目の近似分数をαj=pj /qj=[k0,k1,..,kj]

と定義します。

 

すると,まず,α0=p0/q0=k0/1なので,既約分数の条件:

(p0,q0)=1 から,0=k0,q0=1です。

 

次に1=p1/q1より(p1,q1)=1であり, 

α1=p1/q1=k0+1/k1=(p01+1)/k1です。

そこで,(p01+1,k1)=1 と仮定すると,p1=p01+1,

1=k1=q01 です。

 

しかし,このとき,実際,q0=1 なのでp10-q10=1

ですから,整数論の最大公約数についての定理により,

(p,q1)=1 が得られます。

 

よって,p1=p01+1,q1=k1=q01なる等式の成立は間違

いないです。

 

さらに2=p2/q210+1/(k1+1/k2)=k0+k2/(k12+1) 

(k012+k2+k0)/(k12+1) 

(p012+p0+k2)/(k12+1) 

(p12+p0)/(q12+q0) です。

 

そこで,仮にp2=p12+p0,q2=q12+q0とすれば 

21-p12=p01-p10=-1 を得ます。

 

それ故,p2とq2の最大公約数は1,つまり,(p2,q2)=1であり

2,q2は互いに素であってp2/q2は確かに既約分数です。

 

したがって,p2=p12+p0,q2=q12+q0であり, 

21-p12=p01-p10=-1です。

これを繰り返すと, 

αn=pn/qn,pn=pn-1n+p-n-2, qn =(qn-1n+qn-2

であり,nn-1-pn-1n(-1)n-1

となることが予想されます。

 

そこでn-4=pn-1/qn-1についてpn-1=pn-2n-1+pn-3, 

n-1=qn-2n-1+qn-3,pnn-1n-2-pn-1n-2=(-1)n-2

帰納法の仮定とします。

 

αn-1=pn-1n-1[k0,k1,..,kn-1,]

=k0+1/(k1+1/(k2+..1/kn-1)))..)であり,

αn=pn/qn=[k0,k1,..,kn-1,kn]

=k0+1/(k1+1/(k2+..1/kn-1+1/kn) 

なので,

 

これはαn-1=pn-1/qn-1=(pn-2n-1+pn-3)/(qn-2n-1+qn-3)

において,n-1(kn-1+1/kn)に置き換えただけです。

 

よって αn=pn/qn

=(pn-2(kn-1+1/kn)+pn-3)/(qn-2(kn-1+1/kn)+qn-3) 

=pn-2n-1n+pn-3n+pn-21/(qn-2n-1n+qn-3n+qn-2) 

(pn-1n+p-n-2)/(qn-1n+qn-2) を得ます。

 

そこで,(pn-1n+p-n-2,qn-1n+qn-2)=1 なら 

n=pn-1n+p-n-2, qn =(qn-1n+qn-2です。

 

これを仮定するとpnn-1-pn-1n=qn-1n-2-pn-1n-2

=-(-1)n-2=(-1)n-1です。

 

したがって,確かにこの選択で,

(pn,qn)=(pn-1n+p-n-2,qn-1n+qn-2)=1

となります。

 

以上から,帰納法の結論:αn=pn/qn,pn=pn-1n+p-n-2,

n =qn-1n+qn-2,および,pnn-1-pn-1n=(-1)n-1

成立が証明されました。

 

一方,ω=[k0,k1,k2,..]をω=[k0,k1,..,knn+1], 

ただしn+1=[kn+1,kn+2,k2,..]と表現すれば,

ω=[k0,k1,..,knn+1]の右辺は形の上では,

αn+1=[k0,k1,..,kn,kn+1]の右辺のkn+1をωn+1に置き

換えただけです。

 

それ故n+1=pn+1/qn+1=(pnn+1+pn-1)/(qnn+1+qn-1)

の右辺のkn+1をωn+1に置き換えるとωの表式が得られます。

 

すなわち,ω=(pnωn+1+pn-1)/(qnωn+1+qn-1)です。

このとき,次の定理が成立します。

 

[定理]:ωの近似分数αn=pn/qnは数直線上でωの両側から

1つおきにωに単調に収束する。

 

(証明) ω=(pnωn+1+pn-1)/(qnωn+1+qn-1)より, 

nωn+1+pn-1=ω(qnωn+1+qn-1)です。

 

故に,-ωn+1(qnω-pn-)=(qn-1ω-pn-1) です。

ところが,明らかにωn+1>kn+1≧1 ですから, 

|qnω-pn|<(qn-1ω-pn-1| が成立します。

 

ここで.qn =qn-1n+qn-2≧qn-1nでknは1 以上の整数

ですから,n ≧qn-1>0 です。

故に, 0<(1/qn)≦(1/qn-1) です。

 

したがって,

|ω-(pn/qn)|<(qn-1ω-pn-1|/qn≦,|ω-(pn-1/qn^1)| 

が得られます。

 

他方,-ωn+1(qnω-pn-)=(qn-1ω-pn-1)から, 

ω-(pn/qn)=(-1/ωn+1){ω-(pn-1/qn-1)}(qn-1/qn)

ですから,ω-(pn/qn)とω-(pn-1/qn-1)は異符号であり,

 

初項では0=p0/q0=k0<ωより{ω-(p0/q0)}>0

ですが,次の{ω-(p1/q1)}<0 です。

 

そして,また,

{ω-(p2/q2)}>0で{ω-(p2/q2)}<{ω-(p0/q0)}

です。

 

したがって,nが偶数:n=0,2,4,..ではαn=pn/qnは常にωより

小でωより小さい方から次第に単調増加してωに近づきます。

 

他方,nが奇数:n=1,3,5,..ではαn=pn/qnはωより大きい方

から次第に単調減少してωに近づきます。

 

また,ω=(pnωn+1+pn-1)/(qnωn+1+qn-1)より, 

ω-(pn/qn)=(pnωn+1+pn-1)/(qnωn+1+qn-1)-(pn/qn) 

(pn-1n-pnn-1-)/{qn(qnωn+1+qn-1)} 

(―1)n-1/{qn(qnωn+1+qn-1)} ですが,

 

数列{qn}については,漸化式:qn+1=qnωn+1+qn-1

が成立しているので,(qn+1/qn)≧ωn+1>1です。

 

そこで,ある正の数r>1で常にqn+1/qn>rを満たすものが存在

します。

 

したがって,q0≧1,r>1であって,かつ,qn>q0n より, 

n → ∞に対してqn → ∞ですから,|ω-(pn/qn)| → 0

です。

 

以上から,ωの近似分数αn=pn/qnは数直線上でωの両側

から,1つおきにωに単調に収束する。という定理の結論が

示されました。    (証明終わり)

 

再び循環連分数に戻って前に厳密な証明はPendingにしておいた

命題を証明します。以下の命題です。

 

(1)循環連分数は2次の無理数である。

(2) 2次の無理数の連分数展開は循環連分数となる。 

です。これはLagrangeの定理と呼ばれています。

 

(証明)(1)ωを任意の循環連分数とし最初の数項の循環しない部分

をα,循環する部分をσ=[β]として,ω=[α,σ]と書けば,α,β

は有理数であり,σ=[β.σ]なので,σ=β+1/σより,

σ2-βσ―1=0が成立します。

 

βは有理数ですからσは有理数係数の2次方程式

2-βx―1=0 の根です。

 

具体的には,根の公式から,σ={β+(β2+4)11/2}/2です。 

故に1/σ={-β+(β2+4)11/2}/2,ω=α+1/σであって, 

ω={2α-β+(β2+4)11/2}/2により,

(2ω-2α-β)2=β2+4ですがαも有限項の連分数故,有理数

ですからωも有理数係数の2次方程式の根です。

 

以上から,ωは2次の無理数の1つです。

 

(2)逆にωが2次の無理数とすると。2次の無理数の定義により,

ある整数,b,c(ただし,a≠0)が存在してaω2+bω+c=0

が成立します。

 

先の任意の無限連分数に対する表現:

ω=(pnωn+1+pn-1)/(qnωn+1+qn-1)を 

aω2+bω+c=0 に代入すると,各nごとにある整数An,Bn,Cn

が存在してnωn+12+Bnωn+1+Cn0 (n=0,1,2、..)

が満たされます。

 

具体的に書くと, 

(pnωn+1+pn-1)2/(qnωn+1+qn-1)

+b(pnωn+1+pn-1)/(qnωn+1+qn-1)+c=0 より, 

(pnωn+1+pn-1)2+b(pnωn+1+pn-1)(qnωn+1+qn-1)

+c(qnωn+1+qn-1)2=0 

(apn2+bpnn+cqn2n+12

+(2apnn-1+bpnn-1+bpn-1n+2cqnn-1n+1

(apn-12+bpn-1n-1+cqn-12)=0 ですから,

 

n=apn2+bpnn+cqn2, 

n2apnn-1+bpnn-1++bpn-1n+2cqnn-1, 

n=apn-12+bpn-1n-1+cqn-12

です。

 

αn=pn/qn → ωでωは有限な実数ですから整数pn,qnは有界

であり,したがって,それらの高々2次式であるAn,Bn,Cnも有界

な整数です。

つまり,An,Bn,Cnのそれぞれには最大値と最小値があります。

 

そこで,整数係数の2次方程式

n2+Bnx+Cn=0 (n=0,1,2、..)の個数は

有限個しか有り得ません。

 

そこで,An2+Bnx+Cn=0 (n=0,1,2,..)は実は有限個

を除いて全てが同じ2次方程式であり,これが無数にあります。

 

その異なる方程式の根の全てを改めてω12,..と添字を付けて

m番目より後の項は全てωm+1が満たすのと同じ2次方程式の根

となるように順序を並べかえることができます。

 

すなわち,[ω12,..,ωmm+1m+1、..ωm+1]

=[ω12,..,ωm,ωm+1] です。

 

元々,n→ ∞ではωm+1→ωなのでωm+1が満たす無数の方程式は

ωが満たす方程式の根であるはずです。

すなわち,n → ∞ではAn → A,Bn → B,Cn →Cであり,無理数

ωはAx2+Bx+Cn0 の根であって,A,B,Cは整数です。

 

以上から2次の無理数ωの連分数展開は常に循環連分数であること

が示されました。   (証明終わり)

 

さて,dが2以上の自然数で平方数でないとき,a,bを有理数

としてω=a+b√dの形の全ての実数ωは有理数係数の

2次方程式:(x-a)2-b2d=0 の根ですから2次の無理数です。

逆に任意の2次の無理数ωはある整数d≧2と有理数a,bについて

ω=a+b√dの形に書くことができます。

 

ω=a+b√dを1根とする2次方程式:

(x-a)2-b2d=0 のもう1つの根a-b√dをωの共役

と呼び,これをω=a-b√dと表わすことにします。

次の定理が成立します。

 

[純循環連分数に対するGalois(ガロア)の定理]

2次の無理数ωの連分数展開が初項から直ちに循環が始まる

純循環連分数になるための必要十分条件はω>1 ,かつ,

-1<ω<0 が成立することである。

 

(証明)まず,ωは2次の無理数でω>1,かつ,-1<ω<0 が

成立しているとします。

 

ω=[k0,k1,k2,..]として,これを,

ω=[k01]=[k0,k12]=...=[k0,k1,..,kn-1n]

と置くと,ωn1,かつ,-1<ωn<0 (n=0,1,2,..)

が成立します。

 

これは帰納法によって証明することができます。

 

まず.ω=[k01]=k0+1/ω1より, ω1=1/(ω-k0)

ですが,ω=[k0,k1,k2,..]より,0<(ω-k0)<1なので,

ω1>1です。

 

また, ω=k0+1/ω1より,ω=k0+1/ω1ですから,

ω1=1/(ω-k0)です。

 

そして,-1<ω<0 なので,-(1+k0)<(ω-k0)<-k0

です。

 

(k0-ω)>0かつ,((k0-ω)>k0であり, 

故に,,1/ω<1/(k0-ω)>1/k0≦1です。

そこで,-1<1/(ω-k0)<0,つまり,-1<ω1<0 です。

 

ここで, ωn-1>1,かつ,-1<ωn-1<0 と仮定します。

 

ところが,明らかに,ωn-1=[kn-1n]=kn-1+1/ωnであり, 

ωn-1=kn-11/ωnです。

 

ωn1/(ωn-1-kn-1),ωn=1/(ωn-1-kn-1)で,ωn-1>1,

かつ,-1<ωn-1<0 ですから,

すぐ前で,ω>1,かつ,-1<ω<0の前提から,

ω1=1/(ω-k0),ω1=1/(ω-k0)について

ω1>1,かつ,-1<ω1<0,を示したのと同じ方法で

ωn>1,かつ,-1<ωn<0 を示すことができます。

 

ωn[knn+1]=kn+1/ωn+1n=kn+1/ωn+1なので,

-1/ωn+1=kn+(-ωn)で,0<(-ωn)<1より,

n<(-1/ωn+1)<kn+1ですから,kn=[-1/ωn+1]

を得ます。

 

ただし,最後のkn=[-1/ωn+1]では,[ ]はGauss記号

を意味します。

 

ところが,ω=[k0,k1,k2,..]=[k0,k1,..,kn-1n]

は2次の無理数なので,この右辺の連分数展開は,ある項から循環

します。

 

したがって,m>nなる添字m,nが存在してkm=knm=ωn.

かつ,ωm=ωnが成立します。

 

ところが,km=[-1/ωn+1],kn=[-1/ωn+1]ですから

ωm=ωnの成立はm-1=kn-1を意味します。

 

結局,km=knm=ωn.から,km-1=kn-1m-1=ωn-1しと添字

を1つずつ下げて等式の成立を導くことができるため,

ω=ω0=ωm-n が結論され,ωが純循環であることがわかります。

 

逆に,ω=[k0,k1,k2,..]が純循環連分数なら,  

ω=[0,k1,..,km]=[k0,k1,..,km,ω] です。

 

αn=pn/qn=[k0,k1,..,kn]として, 

ω=(pnωn+1+pn-1)/(qnωn+1+qn-1)であり,循環連分数なら

あるnより先ではωn+1=ωなので,

ω=(pnω+pn-1)/(qnω+qn-1)です。

特に,純循環なので 

ω=ω0=ω1-..=ωn=ωn+1=..ですから,結局,nに無関係

ω=(pnω+pn-1)/(qnω+qn-1)となりますから 

nω2(qn-1-pn)ω-pn-1=0 が成立します。

 

ここで,f(x)=qn2+(qn-1-pn)x-pn-1と置くと,

このxの2次関数のx2の係数qnは正であって,

f(0)=-pn-1<0 ,かつ,f(-)=qn-qn-1+pn-pn-1>0 

です。

 

何故なら,以前の議論でpn=pn-1n+pn-2,qn=qn-1n+qn-2

でしたから,n-pn-1=pn-1((kn-1)+pn-2>0,

n-qn-1=qn-1((kn-1)+qn-2>0 であるからです。

 

また,f(1)=(qn+qn-1)-(pn+pn-1)ですが,これは負の数です。

 

何故ならn=pn/qn>1,かつ,αn-1=pn-1/qn-1>1 なので, 

n<pn,1かつqn-1<pn-1 だからです。

 

以上から,f(x)は座標平面上で下に凸な放物線で

f(-1)>0,f(0)<0,f(1)<0 です。

 

したがって,2次方程式f(x)=0の2根の一方はx=-1と

x=0の間にあり,もう1つはx=0よりも大きい側にあります。

したがって,ω>1,かつ,<-1<ω<0と結論されます。

(証明終わり)

※フランスの天才数学者エヴァリスト・ガロア(E.Galois)

は20歳で決闘で倒れる前夜に有名な「代数方程式がベキ根に

よって解けるための必要十分条件」の論文を残しましたが,

連分数に関する上記の定理はさらに若き日のガロアが残した

ものらしいです。

 

 次は,「Galoisの定理」の応用です。

 [Lagrange(ラグランジュ)の定理]

 2以上の正の整数で平方数でない数dの平方根√dの連分数展開

 √d=[k0,k1,k2,..]は,初項のすぐ次の第1項から純循環連分数

 である。 

 (※実際,前に,√3={1,1,2}なることを見ました。)

 

(証明) √d=[k0,k1,k2,..] なら,まず,明らかに

 k0=[√d]です。

 

そこで,今,ω=k0+√dと置けば,ω=k0-√dです。

このとき,明らかにω>1,かつ,-1<ω<0 です。

 

それ故,Galoisの定理によりωの連分数展開は純循環連分数です。

 

そして,[ω]=k0+ [√d]=2k0,かつ,

ω-k0=√d=[k0,k1,k2,..] ですから,

 

ω=[2k0,k1,k2,..]=[2k0,k1,k2,.kn-1] 

=[2k0,1,k2,.kn-1,2k0] を得ます。

 

以上から, √d=ω-k0=[k0,1,k2,.kn-1,2k0]

と書けます。  (証明終わり)

 

 あとは,もう少しなのですが,ここで次回に続きます。

 ブログを書くという作業も昔より疲れるので少し書いては

 休んでいます。

| | コメント (1) | トラックバック (0)

2015年2月14日 (土)

連分数と近似分数(1)

 Happy。。。バレンタイン。。


 久しぶりに科学記事をアップします。なんとか復活です。!!


 今回のテーマは2013年の入院中に学んだときのノートがタネです。

 2013年の8月に右足人指指切断手術のため順天の形成外科にその年

2回目の入院したときは,最初に持参した理系関係の本は「数論入門講義」(J.S.Chahal著:織田進訳;裳華房),および,ブルーバックスの「数論入門」

(芹沢昭三著;講談社)の2冊だけでした。


私,近年,自宅ではほとんど数論はやらないのですが,長期入院中はいつも

ヒマで退屈なことがわかってたので,できるだけ過去に興味があって購入は

したけれど自宅ではほとんど読まなくなった系列の本を持参するようにして

います。


 そして,このときは,理系の「フェルマーの大定理」のワイルズ(Wiles)など

正統派の証明手順の中で重要な役割を果たす楕円曲線の有理点に

ついて基礎的知見が詳述された前者の専門書,および,関連した軽い読み

物としてブル-バックスの数論の書を持参しました。

 この後者のブルーバックスは入院中にひと通り精読したのですが,そのうちの原始根関連については以前,2013年10月退院直後に記事にしました。

(↑※2013年11・10の記事「原始根と指数(1)」に始まる「原始根と指数」(1~(4)のシリーズ記事参照)

 一方,第4章の連分数については他の書物にない珍しいものなので,,いつ

かはブログに書こうと思っていましたが,テキスト上では表記が結構ややこ

しいため,これはずっとPendingにしてましたが,今回敢えてテーマに選んだ

のでした。 


 ところで,最近,今更ながらご指摘を受けたこともありましたが,本文末に

参考文献と書きながら,ほぼ本のその部分の丸写し同然の記事もある

でしょう。

 今回もほぼ丸写しかも知れません。


 そもそも,高校までは理数系科目はそこまでしなくても勉強できましたが,

45年くらい前の大学時代から今も,ですが,さらっとは読めない類の本や

論文は,和書でも洋書でも基本的にそれを読んで解釈しながら

(洋書なら日本語訳して)そのままノートに付けるというのが私の読書

法,勉強法でした。


(※まあ頭が悪くスグ理解できる方じゃないので,これ,マナブというよりマネブ

という感じですかネ。。言い訳ですが,自分lで発見したモノでないなら所詮学問はマネですが。。。)


そのうち,後から読み返したときにノートよりも字の小さく目が悪くなりつつあった自分には読み辛いタネ本を持ち出して参照しなくてもノートだけで事が足りるように書くようになったので,最低でも元本のその項目全部,それに理解できないとき自分なりに行間を埋めるというプラスαで,ノートの方が幾分内容豊富なハズですが,中には単に丸写し同然の場合もあるかもしれません。


 でも元々,ブログは個人の日記ですし,私自身は自分の消えない回顧録の

ツモリで自己満足的なモノとして書いています。


 もっともブログは個人の覚え書き,日記とはいってもある意味全世界に

公開して,一応少しは読者もいます。また,少しばかり自己顕示欲も満た

されます。

 近頃の言論の自由や表現の自由と同じく自由だからといって誹謗中傷

のようなモノは書かず,一応自分の書いてしまったモノに責任は必要です。


 まさか全部の科学記事が私のオリジナルであるというような誤解は

されないにしても,結局,科学モノは元文献さえ挙げておけば盗作というより,

むしろ紹介や宣伝にでもなると軽い気持で開き直っています。


 あくまでも自分の自己満足主体でブログを書いてます。 


 さて,連分数についてはその存在自体はもっと前から知ってましたが,

 これに最初,特に注目したのは,1980年代始めの頃,勤務していた環境

 アセスメントの会社での大気汚染計算業務に関連して流体力学を勉強

 し,遅い層流でのStokes(ストークス)近似やOseen(オセーン)近似に

 ついて調べたときでした。


 当時は,1928年の古いGoldsteinの論文のコピーを日大数学科助手を

 していたM先輩に頼んで取り寄せてもらって読むと,その中でOseen

 近似の厳密解がレイノルズ数Rのベキ展開で与えられ,その導出過程

 で連分数が使用されていました。


 でも,記号式の定義さえ不明で,結局その部分はワケがわかりませんでした。


 しかし,,厳密解とはいっても,それはどうせニュートン流体を想定したとき

 に成立するナビエ・スト-クス方程式自体の解ではなく その近似方程

 式における解に過ぎないので">それ以上深くは追求せず,当時そのまま

 スルーしました。

(↑※2007年7/30の記事「遅い粘性流(4)(Oseen近似)」を参照)


 さて,,芹沢さんの書物の第4章連分数に従って手順を追ってみます。
;">

この章の始まりの紹介文を見たときには,これは円周率πなど超越数

の最良近似分数を求める話かな?と思っていたのですがそれについて

は入門程度で,主に平方根や整数係数の2次方程式の解である無理数

を連分数で近似する分数近似の話が主体でした。

それはそれで私には連分数自体が目新しい話で,πなどの近似に

ついては,いつになるか?わかりませんが改めてやろうと思います。


 §1.無理数の近似値
 無理数を定義する1つの流れとしては切断(cut)と呼ばれる有理数の集合

を実数と定義し,そのうち有理数でないものを無理数と定めるという謂わ

ゆるDedekind(デデキント)の切断があります。


 もう1つの流れはCantor(カントール)によって基本列と呼ばれた有理数列

を実数とみなす方法です。 


 私は,これらは似たようなものだと思いますが,同じ概念を表現したもの

なのでそれは当然といえば当然でしょう。


 しかし,,数学の基礎部分の公理の周辺の概念は細心の厳密さが要求

されるので,私のような数学的にはアバウトな物理屋の直感は当てに

はならないとは思っています。

例えば,無理数の1つである3の平方根√3の小数による近似は,高校

では「ひとなみにおごれや・・」と記憶したものです。


 これは,√3=1.7320508..のことですが,Cantor風に書けば,√3は

ある数列:a={an}n=1,2,.. ,or  {a1,a2,a3,a4,..,an,..}で与えられると考えます。

ただし,,a1=1,a2=1.7, a3=1.73. a4=1.732,,..,であり; 結局,

√3={1,1.7,1.73.1.732,..}と定義されます。


1.7320508..という表現の代わりに,10進小数の列{1,1.7,1.73.1.732,..}

に書き換えたからといって,何の意味があるのか?と常人の感覚

では訝しく感じるのですが,

少なくとも無限に続く小数というのは数学的には曖昧な概念で

確定的に定義されたものではないので,この数列がこれを定義した

ものと見なすという意味はあります。


 小数列1,1.7,1.73.1.732,..,は,分数では1,17/10,173/100.1732/1000です。

元々有理数は分数で定義され,小数というのは単に分母が1,10,100,1000,

.という10のべき乗である分数に過ぎません。

実際には,√3=1.7320508.は1,17/10,173/100.1732/1000..という列より,

もっと収束の早い分母が10のべき乗ではない分数列があります。

以下では,,結局,こうした近似分数列につながる連分数について述べる

予定です。 

例えば,連分数を用いて作った近似分数の列では,√3は17/10の次の

項は分母が100の173/100ではなく,71/41=1.7317で与えられる>こと

がわかります。 

では連分数とはどのようなものでしょうか?

これは,このブログのようなテキストのテンプレート上では表現が難しい

のですが。。。


 例えば, 2+1/(5+1/(8+1/..)  のような感じです。

 

 ところで,実数には代数的数と超越数の2種類があり,代数的数 

は有理数係数の代数方程式の根であるような実数であり超越数は 

それ以外の実数です。

 

 当然のことですが,代数的数には有理数と無理数がありますが, 

超越数は全て無理数です。

 

 √3は2次の代数方程式x2-3=0の根ですから,1つの代数的数

です。

 

 一方,円周率πやeは超越数です。

 

 これについては本ブログでは2007年5/27の過去記事 

代数的数と超越数」,および,2007年7/23の「eとπの超越性 

 があるので,これも参照してください。

 

 §4.有理数の連分数展開  

 本節では,まず,無理数をとりあえず小数点下6桁目を四捨五入 

した有理数で近似表現します。

 

 そして,その近似有理数を連分数で表現することをで近似すること

を試みます。

 

 すなわち,まず,√3 ~ 1.73205,3√2 ~ 1.25992,e ~ 2.71828, 

 π ~ 3.14159 etc.です。 

 a=1.73205とおくと,a=1+0.73205ですが,これは分数表記 

では­=173205/100000=1+73205/100000です。

 

 そして,100000/73205=1+26795/73205ですから, 

a=1+1/(1+26795/73205)を得ます。

 

さらに,73205/26795=2+19615/26795ですから, 

a=1+1/(1+26795/73205)1+1/{1+1/(2+19615/26795)} 

です。

 

 さらに, 26795/19615=1+7180/19615より, 

a=1+1/{1+1/(2+1/(1+7180/19615))} です。

 

 これをずっと繰り返すのですが,有理数なら有限回で終わります。

 

 系統的に行なうため, 173205と100000の対にユークリッド(Euclid) 

の互除法を適用します。

 

 173205=10000×1+73205,100000=73205×1+26795, 

73205=266795×2+19615,26795=19615×1+7180, 

19615=7480×2+5255,7180=5255×1+1925,  

5255=1925×2+1405,1925=1405×1+1+520, 

1405=520×2+365,520=365×1+155,365=155×2+55, 

155=55×2+45,55=45×1+10,45=10×4+5,10=5×2 

です。

 

 こうして,173205と100000の最大公約数は5であるということが 

わかるのですが,このことから,結局, 

 a=173205/100000=1+26795/100000 

=1+1/(2+19615/26795)1+1/{2+1/(1+7180/19615) 

=1+1/[2+1/{1+1/(2+5255/7180)}]  

..=1+1/(1+/(2+1/(1+1/(2+...+1/(4+1/2) 

 

なる連分数表示が得られます。

 

 この表現はスペースをとり過ぎるので,整数のみを並べて,  

a=1.73205=[1,1,2,1,2,1,2,1,2,1,2,2,1,4,2]と書くこと 

にします。

 

 例えば,371/114を連分数展開すると,

 互除法が371=114×3,114=29×3+27,29=27×1+2, 

 27=2×13+1,2=2×1なので,

 371/114=3+1/[3+1/{1+1/(13+1//2)}] となります。

 

 これを371/114=[3.3.1,13,2] と表現するわけです。

 

 最後に,「有理数の連分数展開は有限である。 

逆に有限連分数は有理数を表わす。」

 

 または,これの対偶として,  

「無限連分数は無理数を表わす。 

無理数の連分数展開は無限連分数となる。」

を本節の結論として記述しておきます。

 

§5.循環連分数

 前に有理数についてやったように,無理数√3を連分数展開 

します。

 

これには√3がx2=3の根であることを利用します。

 

まず,ω=√3-1と置きます。 

すると,(ω+1)2=3より,ω(ω+2)=2です。

 

故に,ω=2/(ω+2)=1/(1+ω/2)=1/{1+1/(2+ω)} 

=1/{1+(1/2)/(1+ω/2)}  

1/[1+1/{2+2/(2+ω)}] 

=1/[1+1/{2+1/(1+ω/2)}]  

1/[1+1/{2+1/(1+1/(2+ω))}=..  

です。

 

この展開は無限に続きます。

 

それ故, √3=ω+1=[1,1,2,1,2,1,2,1,2,..]と表わすことがで 

きますが,このように,何個かの項がまとまりとなって,無限に同じ 

列を繰り返す連分数を循環連分数といいます。

 

そして,こうした無限連分数展開の繰り返す講の塊りを循環節と呼び 

特にこれらに下線を引いて表わすことにします。

 

今の例では,√3=ω+1=[1,1,1,2,1,2,1,2,1,2,..]なので,  

これを,√3=[1,1,2]と書くわけです。

 

 もしも初項から直ちに循環するなら,この無理数の展開連分数を 

純循環連分数といいます。

 

ただし,連分数展開の初項は,単に整数を加えたり減じたりする 

だけで消すことができるのですから,これはさほど重要ではあり 

ません。

 

循環小数の場合,例えば1/7=0.142857,1/13=0.076923 

ですが,a=0.142857と置けば, 

これは10000000a-a=142857,つまり999999a=142857から 

逆にa=1/7を導くことが可能です。

 

一方,循環連分数ωをω=[1,1,2]と置くと,ω=[1,σ],σ=[1,2] 

と表わすことができて,このσはσ=[1,2,σ]と書けます。

 

そして,[1,2,σ]=1+1/(2+1/σ)=(σ+1)/(2σ+1)ですから, 

σ=(3σ+1)/(2σ+1)より,2σ2-2σ+1=0 です。

 

そして, σ>1ですから,σ=(1+√3)/2です。

 

したがって,ω=[1, σ]=1+1/σ=√3を得ます。

 

こうして,循環小数から簡単な計算で対応する有理数である分数 

を得たのと同様に循環連分数から無理数の√3を逆算できること 

がわかりました。

 

念のため,もう1つの具体例:ω=[2,3]の場合,つまり  

ω=2+1/[3+1/{2+1/(3+1/(2+..))}の場合のωを 

求めてみます。

 

ω=[2,3,ω]=2+1/(3+1/α)=(7ω+2)/(3ω+1)より, 

2-6ω-2=0 です。

 

ω>0ですからω=(3+√15)/3=2.29099..を得ます。

 

 循環連分数の別の例として,aを正整数として

ω=[]=[a,a,a,..] 

=a+1/[a+1/{a+1/(a+..)}]  

の場合:ω=[]=[a,ω]=a+1/ω,

 

故にω2-aω-1=0 より, ω={a+(a2+4)1/2}/2 です。

 

特に[1]=[1,1,1,..]=1+1/[1+1/{1+1/(1+..)}]は1では 

なくて[1]=(1+√5)/2です。(フィボナッチ数列)

 

ここで2次の無理数の定義です。 

[定義]:有理数係数の2次方程式の根となる無理数を2次の無理数 

という。

 

2次の無理数については,次の命題を示すことができます。

 

「2次の無理数の連分数展開は循環連分数となる。 

逆に循環連分数は2次の無理数である。」

です。

 

一方,超越数である自然対数の底:eの近似有理数は,  

e=1+1/1!+1/2!+1/3!+1/4+1/5!+..=2.71828.. 

から与えられます。

 

まず,eの近似有理数としてe1=2.71828と置いてこれの連分数 

展開をしてみます。

 

12.71828=271858/100000ですから,271828と100000 

について,Euclidの互除法を実行します。

 

271828=100000×2+71828,100000=71828×1+28172, 

71828=28112×2+15484,28172=15484×1+12688, 

15484=12688×1+2796,12688=2796×4+1504,  

2796=1504×1+1292,1504=1292×1+212, 

1212=212×6+20.212=20×10+12,  

20=12×1+8,12=8×1+4,8=4×2 

です。

 

したがって,e1=[2,1,2,1,1,1,4,1,1,6、10,1,1,2]です。

 

この展開は循環的ではないのですが,なんらかの規則が有りそう 

に見えます。

 

もしも分子が1の分数にこだわらないなら, 

e=2+2/(2+3/(3+4/(4+5/(5+..という  

美しい規則性があります。

 

πについては,Pending..

 

さて,無理数ωの無限連分数展開:ω=[k0,k1,k2,k3,..] 

の右辺の整数列のうち,添字がjのkjまでで止めて得られる 

分数=有理数をαjとして,これを無理数ωの第j近似分数と 

呼ぶことにします。

 

そしてjは既約分数の形ではαj=pj/qjと書けるとします。

 

つまり,pj とqjは互いに素な整数であるとします。

 

αj=pj /qj=[k0,k1,..,kj] です。

 

例えば,ω=√3=[1,1,2]=[1,1,2,1,2,1,2,..] なら,

α1[1,1]=1+1/1=2, 

α2=[1,1,2]=1+1/(1+1/2)=5/3=1.6666.., 

です。

 

α3[1,1,2,1]=1+1/{1+1/(2+1/1)=7/4=1.75,  

α4[1,1,2,1,2]=1+1/[1+1/{2+1/(1+1/2)}] 

=19/11=1.7272727..,

これを繰り返して,結果だけ書くと,α11=1351/780=1.7320513

が得られます。 

 ヒースの研究によれば古代ギリシャのArchimedes(アルキメデス)

 は証明無しで,α8=265/153<√3<1351/780なる不等式を得ていた

 ということです。

 また,日本の和算の学者竹部建部賢宏(1684-1739)は,その著書

「級数算経」の中で,連分数展開によって円周率πをその近似

 分数から,41桁まで求めているそうです。

 ところで,理科年表によれば,太陽が同じ位置に観測される

平均周期=1年は,正しくは365日と5時間48分46秒=約365.2422日

です。

そこで,有理数αをα=365.2422=3652422/10000

=[365,4,7,1,3,4,1,1,1,2]

と置きます。

 そして無理数ωの場合と同じく有理数

α=[365,4,7,1,3,4,1,1,1,2]においても右辺の整数列の添字を

順に 0.1,2,..として添字jの整数までで止めて得られる分数

をαjとします。

 すると,まず,α0=365ですが,このときのαとの誤差は0.2422日

です。

次に1=365+1/4=365.25で,これのαとの誤差は0.078日です。

そこで4年間に1度,1年が366日の閏年にすれば,1年当たりの

平均誤差が0.078日に抑さえられます。

さらに2=365+1/(4+1/7)=365+7/29 ~ 365..24137931..

なので,これだとαとの誤差は約0.0082日です。

そこで,4年間に1度の閏年ではなく29年間に7度の閏年とした

方が誤差が一桁小さくなります。

あるいは3=365+1/|4+1/(7+1/1)}

=365+8/33 ~ 365.242424..なら平均誤差は0. 00022日ですから

33年間に8度の閏年の方がもっとよしです。

 さらに4=365+31/128 ~ 365.2421875,128年間に31度の閏年

で誤差は0.00001日です。

α5=365+132/545 ~ 365.242201834では,さらにαとの誤差は

縮まります。

 現在のグレゴリオ暦では基本的に西暦の年数が4で割り切れれば

閏年てすが,100で割り切れる場合で400で割り切れないなら閏年から

除外されます。

 つまり,西暦2000年は閏年ですが1900年や未来の2100年は閏年で

はないのです。366日になるのは,400年に100-3=97回ですね。

 

 これなら,1年の平均日数は365+97/400=365+0.2425 です。

 長くなったしきりがいいいので,ここで一旦終わって続きは次の

 記事にします。

 久しぶりに数学記事というか,科学記事をやっとのことでアップ

 できましたが,どうも整理がむずかしく,復活の科学記事としては

 ややテーマの選択を誤ったようですね。

 2013年の入院中に書いたネタノートからブログ用に記事をまとめる

 のに2ヶ月もかかってしまいました。

 しかし,とにかくこうした記事もセッセと書かないと,ここは

 「TOSHIの宇宙」ではないと思うし,

 植物人間やひどい認知症のように,まるで家畜のように食っちゃ

 寝で生命を維持してるだけでもなく,PCやTVなどそれなりに受け身

 的な娯楽もあり,本来怠け者の極楽トンボには楽なのですが,

 結局,私の緒場合は生きていく気力も枯渇してしまうような気

 がするので,なんとかブログ書き程度のモチベーションは維持

 したいものです。(つづく)

| | コメント (0) | トラックバック (0)

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の合同式版と考えられます。

 

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

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

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

ここで終了します。

| | コメント (0) | トラックバック (0)

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回で終わると書いた手前もあり

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

| | コメント (0) | トラックバック (0)

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時間やって頂き,そしてほぼ

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

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

 

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

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

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

| | コメント (0) | トラックバック (0)

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がフリ-ズして徒労が重なるとイヤになって

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

| | コメント (0) | トラックバック (0)

2013年10月23日 (水)

数論関係の過去記事(退院後第3報)

 このところ自宅で看護,介護のサービスを受ける合間に,病院で勉強

 した数論関係についての記事を準備中でしたが,

 

 以前よりもはるかに遅筆になっていて,あまりにもブログ記事の

 間が開き過ぎるのが気になったので,ツナぎとして,それに必要な

 いくつかの過去記事を再掲することでお茶を濁しておきます。

  

 数論関係の記事については,

 7年前の2006年3月にブログを開始してまもなく,

 量子コンピュータによる瞬時の素因数分解によって如何なる

 暗号も無力化されるという内容を解説した,

 

 2006年5/4の記事:公開キー暗号(神はサイコロ遊びをなさる)

 というのが,最初ですが,ここでは必ずしも必要でない記事なので,

 

 まず2006年9/12のGaussの合同式に関する記事:

 オイラーの定理とフェルマ-の小定理」から再掲載します。

 

  以下,再掲記事の全文です。↓

  

 今日は数論の"オイラーの定理(Euler's theorem)"を証明し,それに

 よって,"フェルマーの小定理(Fermat's little theorem)"を証明する

 方法を簡単に紹介します。

  

 まず,整数の合同式(modular equality)の定義を述べます。

   

 a,nという2つの整数があって,特にnは正の整数(自然数)である

 とします。

 

 "aをnで割ったときの余りがrである。"というのは,

 

 "a,nに対し整数qが存在してa=nq+r, 0≦r≦n-1と

 一意的に表現できる。"

 

 ことを意味します。

 

 そして,

 

 "nをある正の整数とするとき,整数aとbがnを法(modulo)として

 合同であることを,とbそれぞれをnで割ったときの余りが一致

 すること。" と定義します。

 

 あるいは,"(a-b)がnで割り切れる"と述べても同じです。

  

 そして,整数aとbがnを法として合同であることを,

 a≡b(modn)と書きます。このa≡b(modn)なる式を合同式

 と呼びます。

 

 合同であるという関係は,対称律,反射律,推移律を満たす1つの

 同値関係であり,合同式は普通の等式のように両辺に互いに合同

 な数を加えたり引いたり,また掛けたりしても変わりません。

 

 また,ゼロと合同でない数であれば,それで合同式の両辺を割る

 こともできます。

 

 次に,「フェルマーの小定理」というのは,

 

 "ある整数aがあって,それがある素数pと互いに素,

 つまり,(a,p)=1のときには,ap-11(mod p)

 が成立する。"

 

 というものです。

 

ここで,(a,b)は,整数aとbの最大公約数(g.c.d)を意味します。

 

そして,ap-1は,もちろん,a×a×...×aというように,aを(p-1)

回掛けたものを表わしています。

 

これをpで割ったら余りは必ず1である,というのがこの定理の内容

です。これは結構有名なものです。

 

では,「オイラーの定理」とはどのようなものでしょうか?

  

それを説明するため,まず正の整数mに対してmの整数値関数として

オイラー関数(Euler's function):φ(m)を定義します。

 

オイラー関数:φ(m)とは,1からmまでの正整数のうちでmと互いに

素な正の整数の個数のことです。

 

つまり,これは正の整数mが与えられたとき,丁度φ(m)個の

m以下の正整数:1,b2,...,bφ(m)が存在して(bk,m)=1

(k=1,2,..,φ(m))が満たされることを意味します。

 

すると,当然のことですが,1≦φ(m)<mです。

 

そして,「オイラーの定理」というのは,

  

"ある整数aがあって,それがある正整数mと互いに素,

つまり(a,m)=1のときには,必ずaφ(m)1(mod m)が成り立つ。"

 

というものです。

 

これの証明は意外と簡単です。

 

すなわち,(bk,m)=1;bk≦mなるφ(m)個の整数:

1,b2, .,bφ(m)に対して,aとbkの積の全て:

1,ab2,...,abφ(m)を作り,これらを全部掛け合わせる

だけでいいのです。

 

この積は,aφ(m)12...bφ(m)と書けますが,,

i≠jのときijはmを法として決して

合同にはなり得ません。

 

なぜなら,もしi≡aj(mod m)ならa(ij)≡0(mod m)

ですから,a(ij)mで割り切れることになりますが,aは m

と互いに素なので(ij)がmで割り切れるしかありません。

 

ところが,定義によってi≠jのときにはbi≠bjであり,しかも,

iとbj差の絶対値|i-bj|はmより小さくてゼロではない

のですから,これは有り得ません。

 

ですから,i≠jのときには,ijはmを法として決して

合同にはならないわけです。

 

それ故,1,ab2,...,abφ(m)から取った全ての対はmを法

として互いに合同ではなく,しかも,これらは丁度φ(m)個の整数

ですから,それらの各々をmで割ったときの異なるφ(m)個の余り

は,丁度b1,b2,...bφ(m)の全体と一致します。

 

故に,aφ(m)12・・・bφ(m)12・・・bφ(m) (mod m)

となりますが,12・・・bφ(m)はmと互いに素です。

 

したがって,両辺を12・・・bφ(m)で割ることができて,

結局aφ(m)1 (mod m)を得ます。

 

これでオイラーの定理が証明されました。

 

そして,特にmが素数pに等しいなら,φ(p)=p-1なので

「フェルマーの小定理:p-11 (mod p)」が成立することに

なります。

 

記事は以上です。

 

次に,翌2006年9/13の記事「フェルマーの小定理の別証明

の再掲です。

  

前記事の「フェルマー(Fermat)の小定理」ですが,これをワザワザ,

「オイラー(Euler)の定理」から証明したのは少し大げさな気が

します。

  

これはもっと簡単で,恐らくよりポピュラーな方法で証明できる

ので,それも紹介しておきましょう。

 

要するに,x,yを任意の整数,pを任意素数とするとき,

(x+y)p≡xp+yp (mod p)が成立することさえ証明できれば,

任意の整数aに対してap≡a (mod p)が成立することが示せます。

 

 そこで,後はaとpが互いに素なら,a≡0 (mod p)ではないので,

 両辺をaで割ることにより,ap-11 (mod p)が示されるという

 わけです。

 

 具体的には,x,y,zを任意の整数,pを任意の素数とすると,

 (x+y+z)p(x+y)p+zp≡xp+yp+zp (mod p)が

 成立することになりますから,

 

 整数x,y,zの3つを,さらに4つ,5つ..といくら増やしても

 こうした性質が常に成り立つことになります。

 これ数学的厳密には帰納法です。

 

 そこで,もしaが正の整数なら,a=1+1+..+1でありaは1を

 a個加えたもので,もちろん 1p=1ですから,

 p1+1+..+1≡a (mod p)が成立するわけです。

 

 また,a=0 ならap≡a (mod p)は自明です。

  

 他方,aが負の整数ならa=-1-1-..-1ですが,素数pは2以外

 は奇数ですからp≠2なら(-1)p=-1です。

 

 p=2のときも-1≡1 (mod 2)ですから,やはり,

 (-1)2≡-1(mod 2)なので,ap1-1-..-1≡a (mod p)

 が成立します。

 

 では,上の証明で前提とした等式:(x+y)p≡xp+yp(mod p)

 は本当に成立するのでしょうか?

 

 これの成立は,式の左辺を二項展開することで証明することが

 できます。

 

 すなわち,(x+y)p=∑r=0pprp-rですが,p

 r≠0のときはp=p(p-1)(p-2)..(p-r+1)/r!

 です。

 

 右辺の分母のr!の素因数はr≠pのときは全てpよりも小さく

 分子の素数pとは互いに素ですから,pCrはpで割り切れます。

 

 そこで,r=0,pのときは,C0=pCp=1であり,1≦r≦p-1なら

 pCr≡0 (mod p)ですから,(x+y)p(mod p)が確かに成立する

 ことが示されました。

  

 しかし,高校の"順列と組み合わせ"で習ったnCrは組み合わせ

 数を示すものでしたから,これが整数になるのは当たり前といえば

 当たり前ですが,代数的に証明しないと私には何か気持ち悪いです。

 

 というわけで,二重帰納法によって証明してみたいと思います。

 

 そのため,

 a,rを任意整数として,(a;r)≡a(a+1)(a+2)..(a+r-1)

 と定義し,これがr!で割り切れることを帰納法で証明することを考

 えます。

  

 まず,r=1のときには(a;r)=(a;1)=aでありr!=1です

 から,明らかに(a;r)はr!で割り切れます。

 

 そこで,r>1とし,第一の帰納法の仮定として,あらゆるaに対し

 (a;r-1)は(r-1)!で割り切れるとします。

 

 すると,a=1のときには(a;r)=(1;r)=r!ですから,

 このときは(a;r)は明らかにr!で割り切れます。

 

 そこで,第二の帰納法の仮定として,あるaに対しては(a;r)

 がr!で割り切れるとします。

 

 このとき,

 (a+1;r)=(a+1)(a+2)..(a+r-1)(a+r)

 =a(a+1)(a+2)..(a+r-1)+r(a+1)(a+2)..(a+r-1)

 =(a;r)+r×(a+1;r-1)となりますが,最右辺

 の第1項も第2項も仮定によってr!で割り切れます。

 

 以上から,任意のaとrに対して(a;r)はr!で割り切れること

 が証明されました。

 

 ここで,n=a+r-1と置けば(a;r)/r!=nCrですから,

 結局,nCrが常に整数であることが示されたわけです。

 

 ちなみに,「オイラーの定理:aφ(m)1 (mod m)」を

 「フェルマ-の小定理」から証明することもできます。

 

 指針だけを示すと,まずΦ(m)のmが素数pのベキ乗であるとき:

 m=pαのときにオイラーの定理が成立することを証明します。

 

 一般のmの場合は,mを素因数分解すれば証明することができます。

 

 ただし,φ(pα)=pα-pα-1,

 (m,n)=1ならφ(mn)=φ(m)φ(n)など,

 オイラー関数:φ(m)の性質を使う必要があります。

 

 記事最後の二重帰納法の部分については,

 特に松坂和夫著「代数系入門」(岩波書店)を参照しました。(以上)

 

 ここで,今,午前3時過ぎですが,かなり眠くなり糖尿病のせいで,

 全身の痒みが襲ってきたので後は,Pendingにします。

 

 追伸:睡眠後,24日の早朝には,後半の文字が小さいという文字化け

 を修正中にHTMLエラーで1つの間違いを探すのに1時間,

 

 その後,さらに文章を整形中にwindowsのエラーで3時間程度の努力

 が水泡となり,あきらめて朝9時半からの外来診察に出かけました。

 

 (※以後は途中での突然の終わりにヒヤヒヤして中途,中途でアップ

 =保存するの繰り返し...)

 

 午前中は順天堂で先週自宅に送られてきた右足の指用の義足に

 似た靴の装具の微調整,終わってお昼に隣りの東京医科歯科大

 で義歯の修正,午後1時半に終わって丸の内線で池袋まで行き,

 ヤマダ電機でプリンタなど見て雨のため疲労困憊で帰宅,爆睡

 してまた夜中に覚醒...続きを書くもまたも3時間の徒労etc..

 

 翌25日夜,2006年9/28の「数論の演習問題(解答)」から合同式

 やフェルマーの小定理の例題を再掲します。

  

 ちと早いけど,昨日出した問題の解答を与えておきます。

 

 あまりスマートではなく泥臭い解答となりましたが,もっと

 エレガントな方法があればコメントで披露してください。

 

 問1.(2100-1)99を100で割ったときの余りを求めよ。

 (ヒントは 210=1024でこれを100 で割った余りは24である

 ということです。)

   

 (解答) まず, 210=1024≡24(mod 100 )です。

 そして, 242=576≡-24(mod 100)ですから,

 243≡-242≡24(mod100)...etc.になります。

  

 よって2100≡2410≡-24(mod 100)です。

 それ故, 2100-1≡-25(mod 100)ですね。

  

 次に(-25)2=625≡25(mod 100)ですから,

 (2100-1)99≡(-25)98・(-25)≡-25≡75(mod 100)

 である,

  

 というわけで,(2100-1)99を100で割った余りは75である,

 というのが結論です。(以上)

 

 問2. 330≡1+17・31 (mod  312)であることを証明せよ。

  

 (解答) "フェルマー(Fermat)の小定理"によれば,

 330≡1(mod31)です。

 

 よってA をある整数として,330=31A+1と書けますから,

 A≡ 17(mod31)となることを証明すればいいです。

  

 そこで,方針としては315≡1(mod31)か,あるいは,

 315≡-1(mod31)であるかのいずれかなので,

  

 315=31B±1より,330=(31B±1)2≡1±2B・31(mod 312)

 として,±2B≡A≡17(mod31)を示すことにします。

  

 そのために,まず35=243=(31・8-5)と書き,両辺を3乗します。

  

 すなわち,

 315=(31・8-5)3=(31・8)3-15(31・8)2+75・31・8-125

 ≡600・31-4・31-1≡7・31-1(mod 312)ですが,

   

 これをまとめると315≡7・31-1(mod 312)となります。

  

 したがって,A≡-2B=-14≡17(mod31)となるので,

  

 結局,証明の結論である330≡1+17・31(mod 312)

 が得られました。(以上)

| | コメント (0) | トラックバック (0)

その他のカテゴリー

001. 目次 002. 募金・ボランティア 003. 日記・回想 004 訃報 005. 心身・思想・哲学 006. 社会・経済・政治 007. 病気(診察・薬) 008. 恋愛・異性 009 宗教・神話 010 歴史(日本,世界) 011. 将棋 012. TV(ニュース・ドラマ) 013 スポーツ(ニュース・イベント) 014 ノン・フィクション 015 小説・詩・評論 016 漫画・劇画・アニメ 017 演劇・映画・舞踊 018 音楽(日本・西洋・他) 019 タレント(俳優・お笑い) 020 ミュージシャン 021 アイドル・ヒーロー 022 創作 023 シャレ・ギャグ等 024 競馬・toto・賭け事 025 ファッション・風俗 100. 物理学一般 101 教育・学校(物理) 102. 力学・解析力学 103. 電磁気学・光学 104. 熱力学・統計力学 105. 相対性理論 106. 星・ブラックホール・一般相対性 107. 重力・宇宙・一般相対性 108. 連続体・流体力学 109. 物性物理 110. 複雑系・確率過程・非線型・非平衡 111. 量子論 112. 原子・分子物理 113. 原子核物理 114 . 場理論・QED 115. 素粒子論 116. 弦理論 118. 観測問題・量子もつれ 119. 電気回路 200. 問題・解答 201. 自然科学一般 202. 気象・地学・環境 203. 生物学・生理学・生化学 204. 経済学(ミクロ・マクロ・マルクス) 300 数学一般・算数 301. 集合・位相 302. 論理学・数学基礎論 303. 代数学・数論 304. 解析学 305. 複素数・複素関数論 306. 線型代数学 307. 幾何学(トポロジー・他) 308. 微分方程式 309. 確率・統計 310. 関数解析・超関数 311 .数値計算・調和解析・離散数学 312. 公式・特殊関数 501. 商用宣伝・アフィリエイト