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

概要

編集

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

 

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


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

証明

編集

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

 とする。

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

 

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

 

nとPは互いに素だから

  (証明終)

使用例

編集

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

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

よって 

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

関連項目

編集