オイラーの定理 (数論)
提供: miniwiki
2018/6/27/ (水) 16:05時点におけるja>RGAMTAによる版 (Category:レオンハルト・オイラーを追加 (HotCat使用))
数論において、オイラーの定理(Euler's theorem)は初等整数論の最も基本的な定理の一つである。
概要
- [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になる。