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

　今日は数論の"オイラーの定理(Euler's theorem)"を証明し,それによって,"フェルマーの小定理(Fermat's little theorem)"を証明する方法を簡単に紹介します。 

　まず,整数の合同式(modular equality)の定義を述べます。

　ａ,ｎという２つの整数があってｎは正の整数であるとします。

　"ａをｎで割ったときの余りがｒである"というのは,"ａ,ｎに対し整数ｑが存在してａ＝ｎｑ＋ｒ, 0≦ｒ≦ｎ－1と一意的に表現できること"を意味します。

　そして,ｎをある正の整数とするとき,"整数ａとｂがｎを法(modulo)として合同である。"とは,"ａとｂそれぞれをｎで割ったときの余りが一致すること"をいいます。あるいは,"(ａ－ｂ)がｎで割り切れる"といっても同じです。

　そして,整数ａとｂがｎを法として合同であることをａ≡ｂ(modｎ)と書きます。ａ≡ｂ(modｎ)なる式を合同式と呼びます。

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

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

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

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

そして,ａ^p-1は,もちろんａ×ａ×...×ａと,ａを(ｐ－１)回掛けたものを表わしています。これをｐで割ったら余りは必ず１である,

というのがこの定理の内容です。これは結構有名なものです。

では,"オイラーの定理"とはどのようなものでしょうか？ 

それを説明するため,まず正の整数ｍに対してｍの整数値関数としてオイラー関数(Euler's function)φ(ｍ)を定義します。

オイラー関数φ(ｍ)とは,１からｍまでの正整数のうちでｍと互いに素な正の整数の個数のことです。

つまり,正の整数ｍが与えられたとき,丁度φ(ｍ)個のｍ以下の正整数ｂ₁,ｂ₂,...,ｂ_φ(ｍ)が存在して(ｂ_k,ｍ)＝１(ｋ＝1,2,..,φ(ｍ))を満たすことを意味します。

当然のことですが,1≦φ(ｍ)＜ｍです。

そして,"オイラーの定理"というのは,"ある整数ａがあって,それがある正整数ｍと互いに素,つまり(ａ,ｍ)＝1のときには,必ずａ^φ(ｍ)≡1(mod ｍ)が成り立つ。"というものです。

これの証明は意外と簡単です。

すなわち,(ｂ_k,ｍ)＝１;ｂ_k≦ｍなるφ(ｍ)個の整数ｂ₁,ｂ₂, ．,ｂ_φ(ｍ)に対して,ａとｂ_kの積の全てａｂ₁,ａｂ₂,...,ａｂ_φ(ｍ)を作り,これらを全部掛け合わせるだけでいいのです。

この積は,ａ^φ(ｍ)ｂ₁ｂ₂...ｂ_φ(ｍ)と書けますが,ｉ≠ｊのときａｂ_iとａｂ_jはｍを法として決して合同にはなりません。 

なぜなら,もしａｂ_i≡ａｂ_j(mod ｍ)ならａ(ｂ_i－ｂ_j)≡0（mod ｍ)ですから,ａ(ｂ_i－ｂ_j)はｍで割り切れることになりますが,ａは ｍ と互いに素なので(ｂ_i－ｂ_j)がｍで割り切れるしかありません。

ところが,定義によってｉ≠ｊのときにはｂ_i≠ｂ_jであり,しかも,ｂ_iとｂ_jの差の絶対値|ｂ_i－ｂ_j|はｍより小さくてゼロではないのですから,これは有り得ません。

ですから,ｉ≠ｊのときにはａｂ_iとａｂ_jはｍを法として決して合同にはならないわけです。 

それ故,ａｂ₁,ａｂ₂,...,ａｂ_φ(ｍ)から取った全ての対はｍを法として互いに合同ではなく,しかも,これらは丁度φ(ｍ)個の整数ですから,それらの各々をｍで割ったときの異なるφ(ｍ)個の余りは,丁度ｂ₁,ｂ₂,...ｂ_φ(ｍ)の全体と一致します。

故に,ａ^φ(ｍ)ｂ₁ｂ₂・・・ｂ_φ(ｍ)≡ｂ₁ｂ₂・・・ｂ_φ(ｍ) (mod ｍ)となりますが,ｂ₁ｂ₂・・・ｂ_φ(ｍ)はｍと互いに素です。

したがって,両辺をｂ₁ｂ₂・・・ｂ_φ(ｍ)で割ることができて,結局ａ^φ(ｍ)≡1 (mod ｍ)を得ます。

これでオイラーの定理が証明されました。 

そして,特にｍが素数ｐに等しいなら,φ(ｐ)＝ｐ－１なので,フェルマーの小定理:ａ^p-1≡1 (mod ｐ)が成立することになります。　

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

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