オイラーの定理 (数論) From Wikipedia, the free encyclopedia 数論において、オイラーの定理（Euler's theorem）は初等整数論の最も基本的な定理の一つである。 nが正の整数でaをnと互いに素な正の整数としたとき, a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} が成立する。 ここで φ ( n ) {\displaystyle \varphi (n)} はオイラーのφ関数である。 この定理はフェルマーの小定理の一般化であり、この定理をさらに一般化したものがカーマイケルの定理である。 証明 nと互いに素なn以下の正の整数の集合を A = { b 1 , b 2 , . . . , b φ ( n ) } {\displaystyle A=\{b_{1},b_{2},...,b_{\varphi (n)}\}} とする。 この要素のそれぞれにaを乗じた集合 B = { a b 1 , a b 2 , . . . , a b φ ( n ) } {\displaystyle B=\{ab_{1},ab_{2},...,ab_{\varphi (n)}\}} を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、 P ≡ a φ ( n ) P ( mod n ) {\displaystyle P\equiv a^{\varphi (n)}P{\pmod {n}}} nとPは互いに素だから a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} (証明終) 使用例 例えば7^2009の下二桁を求めたいときに、次のように考えることができる。 φ ( 100 ) = 40 {\displaystyle \varphi (100)=40} なので,オイラーの定理から 7 40 ≡ 1 ( mod 100 ) {\displaystyle 7^{40}\equiv 1{\pmod {100}}} . よって 7 2009 = 7 9 × ( 7 40 ) 50 ≡ 7 9 ≡ 7 ( mod 100 ) {\displaystyle 7^{2009}=7^{9}\times (7^{40})^{50}\equiv 7^{9}\equiv 7{\pmod {100}}} ゆえに下二桁は07になる。 関連項目 レオンハルト・オイラー Related Articles
なので,オイラーの定理から
.
