オイラーの定理 (数論)のソースを表示

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

== 関連項目 ==
* [[レオンハルト・オイラー]]

{{DEFAULTSORT:おいらあのていり}}
[[Category:数論の定理]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]
[[Category:レオンハルト・オイラー]]