オイラーの定理 (数論)
証明
nと互いに素なn以下の正の整数の集合を
- とする。
この要素のそれぞれにaを乗じた集合
を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、
nとPは互いに素だから
- (証明終)
使用例
例えば7^2009の下二桁を求めたいときに、次のように考えることができる。
なので,オイラーの定理から .
よって
ゆえに下二桁は07になる。
関連項目
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.