)
オイラーの定理 (数論) - Wikipedia数論において、オイラーの定理（Euler's theorem）は初等整数論の最も基本的な定理の一つである。 概要[編集] nが正の整数でaをnと互いに素な正の整数としたとき, が成立する。 ここではオイラーのφ関数である。 この定理はフェルマーの小定理の一般化であり、この定理をさらに一般化したものがカーマイケルの定理である。 証明[編集] nと互いに素なn以下の正の整数の集合を とする。 この要素のそれぞれにaを乗じた集合 を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、 nとPは互いに素だから (証明終) 使用例[編集] 例えば7^2009の下二桁を求めたいときに、次のように考えることができる。 なので,オイラーの定理から . よって ゆえに下二桁は07になる。 関連項目[編集] レオンハルト・
