📂Number Theory

Proof of Euler's Totient Theorem

Theorem ¹

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

Explanation

At a glance one can see that this is a generalization of Fermat’s little theorem, and indeed the proof is essentially almost identical.

Proof

By the definition of the totient function, among $1 \le b_{i} \le m$ there are exactly $\phi (m)$ values of $b_{i}$ satisfying $\gcd( b_{i} , m) =1$. Let the set of these be $$ B:= \left\{ b_{1}, b_{2}, \cdots , b_{\phi (m)} \right\} $$ Then, since $\gcd(a,m) = 1$, $$ aB = \left\{ ab_{1}, ab_{2}, \cdots , ab_{\phi (m)} \right\} $$ becomes exactly the same set. Therefore $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv ab_{1} ab_{2} \cdots ab_{\phi (m)} \pmod{m} $$ Factoring out $a$ on the right-hand side, $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv a^{\phi (m)} b_{1} b_{2} \cdots b_{\phi (m)} \pmod{m} $$ Since $\gcd( b_{1} b_{2} \cdots b_{\phi (m)} , m ) =1$, canceling it from both sides yields the following. $$ a^{ \phi (m) } \equiv 1 \pmod{m} $$

■