オイラーの定理 (数論)

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

概要 [編集]

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

$a^{\varphi (n)} \equiv 1 \pmod{n}$

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

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

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

$A=\{b_1,b_2,...,b_{\varphi(n)}\}$ とする。

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

$B=\{ab_1,ab_2,...,ab_{\varphi(n)}\}$ を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、

$P\equiv a^{\varphi(n)}P\pmod{n}$

nとPは互いに素だから

$a^{\varphi(n)}\equiv 1\pmod{n}$ (証明終)

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

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

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

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