📂Number Theory

Euler's Totient Theorem Proof

Theorem ¹

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

Description

One can immediately recognize that this theorem generalizes Fermat’s Little Theorem, and indeed, the proof is almost identical.

Proof

By the definition of the Euler’s totient function, there exactly $\phi (m)$ occurrences of $b_{i}$ satisfying $\gcd( b_{i} , m) =1$ among $1 \le b_{i} \le m$. Let’s call this set $$ 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} $$ by grouping $a$ on the right side, we have $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv a^{\phi (m)} b_{1} b_{2} \cdots b_{\phi (m)} \pmod{m} $$ By canceling both sides with $\gcd( b_{1} b_{2} \cdots b_{\phi (m)} , m ) =1$, we obtain the following. $$ a^{ \phi (m) } \equiv 1 \pmod{m} $$

■