オイラーの定理 (数論)

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

概要

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

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

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

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

証明

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「http://localhost:6011/ja.wikipedia.org/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A=\{b_1,b_2,...,b_{\varphi(n)}\}} とする。

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「http://localhost:6011/ja.wikipedia.org/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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になる。

関連項目

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