📂整数論

オイラーのトーシェント定理の証明

定理 ¹

$$ \gcd(a,m) = 1 \implies a^{ \phi (m) } \equiv 1 \pmod{m} $$

説明

この定理がフェルマーの小定理を一般化したものであることがすぐにわかり、実際、証明法もほぼ同じである。

証明

オイラーのφ関数の定義によると、$1 \le b_{i} \le m$ 中 $\gcd( b_{i} , m) =1$ を満たす $b_{i}$ の正確な数は $\phi (m)$ 個存在する。この集合を $$ B:= \left\{ b_{1}, b_{2}, \cdots , b_{\phi (m)} \right\} $$ としよう。すると、$\gcd(a,m) = 1$ だから $$ aB = \left\{ ab_{1}, ab_{2}, \cdots , ab_{\phi (m)} \right\} $$ は全く同じ集合になる。だから、 $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv ab_{1} ab_{2} \cdots ab_{\phi (m)} \pmod{m} $$ 右辺の $a$ をまとめると、 $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv a^{\phi (m)} b_{1} b_{2} \cdots b_{\phi (m)} \pmod{m} $$ $\gcd( b_{1} b_{2} \cdots b_{\phi (m)} , m ) =1$ で両辺を消すことにより、以下を得る。 $$ a^{ \phi (m) } \equiv 1 \pmod{m} $$

■