オイラーの定理 (数論)

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

概要

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

a^{φ (n)} \equiv 1 (\mod n)

が成立する。ここで $φ (n)$ はオイラーのφ関数である。

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

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

A = {b_{1}, b_{2}, . . ., b_{φ (n)}}

とする。

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

B = {a b_{1}, a b_{2}, . . ., a b_{φ (n)}}

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

P \equiv a^{φ (n)} P (\mod n)

nとPは互いに素だから

a^{φ (n)} \equiv 1 (\mod n)

(証明終)

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

$φ (100) = 40$ なので,オイラーの定理から $7^{40} \equiv 1 (\mod 100)$ .

よって $7^{2009} = 7^{9} \times (7^{40})^{50} \equiv 7^{9} \equiv 7 (\mod 100)$

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