オイラーの定理 (数論)

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

概要

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

[math]a^{\varphi (n)} \equiv 1 \pmod{n}[/math]

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

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

証明

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

[math]A=\{b_1,b_2,...,b_{\varphi(n)}\}[/math]とする。

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

[math]B=\{ab_1,ab_2,...,ab_{\varphi(n)}\}[/math]

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

[math]P\equiv a^{\varphi(n)}P\pmod{n}[/math]

nとPは互いに素だから

[math]a^{\varphi(n)}\equiv 1\pmod{n}[/math] (証明終)

使用例

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

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

よって[math]7^{2009}=7^9\times (7^{40})^{50}\equiv 7^9\equiv 7\pmod{100}[/math]

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

関連項目

• レオンハルト・オイラー