オイラーの定理 (数論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

数論において、オイラーの定理(Euler's theorem)は初等整数論の最も基本的な定理の一つである。

概要[編集]

nが正の整数でaをnと互いに素な正の整数としたとき,

が成立する。 ここでオイラーのφ関数である。


この定理はフェルマーの小定理の一般化であり、この定理をさらに一般化したものがカーマイケルの定理である。

証明[編集]

nと互いに素なn以下の正の整数の集合を

とする。

この要素のそれぞれにaを乗じた集合

を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、

nとPは互いに素だから

(証明終)

使用例[編集]

例えば7^2009の下二桁を求めたいときに、次のように考えることができる。

なので,オイラーの定理から .

よって

ゆえに下二桁は07になる。

関連項目[編集]