« 退院。。第2報 | トップページ | 訃報 岩谷時子さん。。 »

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)

 が得られました。(以上)

|

« 退院。。第2報 | トップページ | 訃報 岩谷時子さん。。 »

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

コメント

コメントを書く



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




トラックバック


この記事へのトラックバック一覧です: 数論関係の過去記事(退院後第3報):

« 退院。。第2報 | トップページ | 訃報 岩谷時子さん。。 »