オイラーの定理(トーシェント関数)

内容

$\gcd(a,n)=1$ ならば $a^{\varphi(n)}\equiv 1 \pmod{n}$ が成り立つ。ここで $\varphi(n)$(オイラーのトーシェント関数)は $\{1,\dots,n\}$ の中で $n$ と互いに素な整数の個数を表す。

なぜ正しいのか?

これはフェルマーの小定理を素数を法とする場合から一般の法へと一般化したものである:$\varphi(n)$ 個の、$n$ を法として可逆な剰余に対して同じ置換の議論が成り立つ($1,\dots,p-1$ すべてではなく)。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。