トップQs
タイムライン
チャット
視点
オイラーの定理 (数論)
初等整数論の最も基本的な定理 ウィキペディアから
Remove ads
概要
が成立する。 ここではオイラーのφ関数である。
Remove ads
証明
要約
視点
nと互いに素なn以下の正の整数の集合を
- とする。
この要素のそれぞれにaを乗じた集合
を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、
nとPは互いに素だから
- (証明終)
Remove ads
使用例
例えば7^2009の下二桁を求めたいときに、次のように考えることができる。
なので,オイラーの定理から .
よって
ゆえに下二桁は07になる。
関連項目
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads