数論において、オイラーの定理(Euler's theorem)は初等整数論の最も基本的な定理の一つである。
概要
nが正の整数でaをnと互いに素な正の整数としたとき,
![{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e818f3f88d3e71e569f171dd86f31e1903fdc55)
が成立する。 ここで
はオイラーのφ関数である。
この定理はフェルマーの小定理の一般化であり、この定理をさらに一般化したものがカーマイケルの定理である。
証明
nと互いに素なn以下の正の整数の集合を
とする。
この要素のそれぞれにaを乗じた集合
![{\displaystyle B=\{ab_{1},ab_{2},...,ab_{\varphi (n)}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cfed1c76aed5298ef9ad379b2dbeb787ec219e2)
を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、
![{\displaystyle P\equiv a^{\varphi (n)}P{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd2b8a9b08569155c28418cd970f08e57b5f74ee)
nとPは互いに素だから
(証明終)
使用例
例えば7^2009の下二桁を求めたいときに、次のように考えることができる。
なので,オイラーの定理から
.
よって
ゆえに下二桁は07になる。
関連項目