« 記念日 | トップページ | フェルマーの小定理の別証明 »

2006年9月12日 (火)

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

 今日は数論の"オイラーの定理(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)として合同である。"とは,"aとbそれぞれをnで割ったときの余りが一致すること"をいいます。あるいは,"(a-b)がnで割り切れる"といっても同じです。

 

 そして,整数aとbがnを法として合同であることをa≡b(modn)と書きます。a≡b(modn)なる式を合同式と呼びます。

 

 合同であるという合同式の性質は普通の等式のように両辺に互いに合同な数を加えたり引いたり,また掛けたりしても変わりません。

 

 また,ゼロと合同でない数であれば,それで合同式の両辺を割ることもできます。

"フェルマーの小定理"というのは,"ある整数aがあって,それがある素数pと互いに素,つまり(a,p)=1のときにはap-11(mod p)である。"というものです。

 

ここで,(a,b)は,整数aとbの最大公約数(gcd)を意味します。

 

そして,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)個の整数b1,b2, .,bφ(m)に対して,aとbkの積の全てa1,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であり,しかも,biと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)が成立することになります。 

  

http://fphys.nifty.com/(ニフティ「物理フォーラム」サブマネージャー)                                       TOSHI

http://blog.with2.net/link.php?269343(ブログ・ランキングの投票)↑ここをクリックすると投票したことになります。

    

|

« 記念日 | トップページ | フェルマーの小定理の別証明 »

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

コメント

コメントを書く



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




トラックバック


この記事へのトラックバック一覧です: オイラーの定理とフェルマーの小定理(合同式):

« 記念日 | トップページ | フェルマーの小定理の別証明 »