オイラーの定理 (数論)

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

数論において、オイラーの定理(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になる。

関連項目[編集]