📂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}$$

■