Euler's Totient Function and Euler's Theorem

💡 The Core Insight

The totient function $\phi(n)$ counts coprime residues and simultaneously reveals the multiplicative order structure modulo $n$ : every number coprime to $n$ returns to 1 after exactly $\phi(n)$ multiplications.

Definition

Euler's Totient Function: For a positive integer $n$ , the Euler totient function (or Euler phi function) is defined as

\phi(n) = |\{k \in \mathbb{Z} : 1 \leq k \leq n \text{ and } \gcd(k,n) = 1\}|

That is, $\phi(n)$ counts the number of integers between 1 and $n$ (inclusive) that are relatively prime to $n$ .

Euler's Theorem: If $n$ is a positive integer and $a$ is an integer with $\gcd(a,n) = 1$ , then

a^{\phi(n)} \equiv 1 \pmod{n}

TheoremMain Results

Theorem 1 (Multiplicativity of $\phi$ ): If $\gcd(m,n) = 1$ , then $\phi(mn) = \phi(m)\phi(n)$ .

Theorem 2 (Explicit Formula): If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ is the prime factorization of $n$ , then

\phi(n) = n \prod_{p | n} \left(1 - \frac{1}{p}\right) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)

Theorem 3 (Euler's Theorem): If $\gcd(a,n) = 1$ , then $a^{\phi(n)} \equiv 1 \pmod{n}$ .

Theorem 4 (Prime Power Formula): For a prime $p$ and positive integer $k$ ,

\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)

Proof

Proof of Theorem 4: Among the integers $1, 2, 3, \ldots, p^k$ , exactly those that are multiples of $p$ share a common factor with $p^k$ . The multiples of $p$ in this range are $p, 2p, 3p, \ldots, p^{k-1} \cdot p$ , of which there are $p^{k-1}$ . Therefore,

\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)

Proof of Theorem 1: We use the Chinese Remainder Theorem. Since $\gcd(m,n) = 1$ , the map

f: \mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}

given by $f(x \bmod mn) = (x \bmod m, x \bmod n)$ is a ring isomorphism. An element $x$ is coprime to $mn$ if and only if $x$ is coprime to both $m$ and $n$ . Under the isomorphism $f$ , the units modulo $mn$ correspond exactly to pairs $(u,v)$ where $u$ is a unit modulo $m$ and $v$ is a unit modulo $n$ . There are $\phi(m)$ choices for $u$ and $\phi(n)$ choices for $v$ , giving $\phi(mn) = \phi(m)\phi(n)$ .

Proof of Theorem 2: By Theorem 1, $\phi$ is multiplicative, so

\phi(n) = \phi(p_1^{a_1}) \phi(p_2^{a_2}) \cdots \phi(p_k^{a_k})

By Theorem 4, $\phi(p_i^{a_i}) = p_i^{a_i}\left(1 - \frac{1}{p_i}\right)$ . Therefore,

\phi(n) = \prod_{i=1}^k p_i^{a_i}\left(1 - \frac{1}{p_i}\right) = \left(\prod_{i=1}^k p_i^{a_i}\right) \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right) = n \prod_{p|n}\left(1 - \frac{1}{p}\right)

Proof of Theorem 3 (Euler's Theorem): Let $U_n = \{a \in \mathbb{Z} : 1 \leq a \leq n, \gcd(a,n) = 1\}$ be the set of reduced residues modulo $n$ . Then $|U_n| = \phi(n)$ .

Claim: If $\gcd(a,n) = 1$ and $r \in U_n$ , then $ar \bmod n \in U_n$ . Proof of claim: If $d = \gcd(ar, n)$ , then $d | ar$ and $d | n$ . Since $\gcd(a,n) = 1$ , any common divisor of $ar$ and $n$ must also divide $r$ . Thus $d | \gcd(r,n) = 1$ , so $\gcd(ar,n) = 1$ . Now consider the set $\{ar \bmod n : r \in U_n\}$ . By the claim, each element is in $U_n$ . Moreover, if $ar_1 \equiv ar_2 \pmod{n}$ , then since $\gcd(a,n) = 1$ , we can cancel $a$ to get $r_1 \equiv r_2 \pmod{n}$ . Thus multiplication by $a$ gives a bijection $U_n \to U_n$ . Let $U_n = \{r_1, r_2, \ldots, r_{\phi(n)}\}$ . Then $\{ar_1, ar_2, \ldots, ar_{\phi(n)}\}$ is a permutation of $U_n$ modulo $n$ . Therefore,

(ar_1)(ar_2) \cdots (ar_{\phi(n)}) \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod{n}

a^{\phi(n)} (r_1 r_2 \cdots r_{\phi(n)}) \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod{n}

Let $R = r_1 r_2 \cdots r_{\phi(n)}$ . Since each $r_i$ is coprime to $n$ , we have $\gcd(R, n) = 1$ . Therefore, we can cancel $R$ from both sides:

a^{\phi(n)} \equiv 1 \pmod{n}

□

∎

⚠️ Common mistake

Common Error: Students often try to apply Euler's Theorem without checking that $\gcd(a,n) = 1$ . For example, $2^{\phi(6)} = 2^2 = 4 \not\equiv 1 \pmod{6}$ because $\gcd(2,6) = 2 \neq 1$ . The coprimality condition is essential—the theorem simply doesn't hold otherwise. Similarly, $\phi(n)$ is not the number of primes less than $n$ (that's the prime counting function $\pi(n)$ ).

mathematician

Leonhard Euler (1763) — Introduced the totient function and proved Euler's Theorem in his paper "Theoremata arithmetica nova methodo demonstrata," generalizing Fermat's work and founding modern multiplicative number theory.

visualization

Example1

Computing $\phi(360)$ using the explicit formula: First, find the prime factorization: $360 = 2^3 \cdot 3^2 \cdot 5$ . Using Theorem 2:

\phi(360) = 360 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right)

= 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5}

= 360 \cdot \frac{8}{30} = 360 \cdot \frac{4}{15} = 96

We can verify using multiplicativity:

\phi(360) = \phi(2^3) \cdot \phi(3^2) \cdot \phi(5) = (2^2 \cdot 1) \cdot (3 \cdot 2) \cdot (4) = 4 \cdot 6 \cdot 4 = 96

Therefore, there are exactly 96 integers between 1 and 360 that share no common factors with 360.

Example2

Using Euler's Theorem to find $7^{222} \bmod 10$ : First, check: $\gcd(7, 10) = 1$ ✓ Compute $\phi(10) = \phi(2 \cdot 5) = \phi(2)\phi(5) = 1 \cdot 4 = 4$ . By Euler's Theorem, $7^4 \equiv 1 \pmod{10}$ . Now divide the exponent: $222 = 4 \cdot 55 + 2$ . Therefore,

7^{222} = 7^{4 \cdot 55 + 2} = (7^4)^{55} \cdot 7^2 \equiv 1^{55} \cdot 49 \equiv 49 \equiv 9 \pmod{10}

This technique is fundamental in modular exponentiation algorithms used in cryptography.

Counterexample

Why the coprimality condition is necessary: Consider $a = 6$ , $n = 9$ . We have $\phi(9) = 6$ , but $\gcd(6,9) = 3 \neq 1$ . Computing: $6^6 = 46656 = 5184 \cdot 9$ , so $6^6 \equiv 0 \pmod{9}$ . Clearly $0 \not\equiv 1 \pmod{9}$ , so Euler's Theorem fails completely when the coprimality hypothesis is dropped. The issue is that $6$ is not a unit in $\mathbb{Z}/9\mathbb{Z}$ —it's a zero divisor, since $6 \cdot 3 \equiv 0 \pmod{9}$ . The proof fundamentally relies on being able to cancel common factors, which requires working within the group of units.

🧠 Intuition

Visual mental model: Imagine a clock with $n$ hours. The totient $\phi(n)$ counts which hour marks are "reachable by coprime steps"—if you can walk around the clock taking steps of size $k$ where $\gcd(k,n) = 1$ , you'll eventually hit exactly $\phi(n)$ different hours. Euler's Theorem says: if you start at 1 and keep multiplying by any coprime number $a$ , after exactly $\phi(n)$ steps you return to 1. The totient measures the "period of multiplication" modulo $n$ . For prime $p$ , every nonzero element works ( $\phi(p) = p-1$ ), which is why Fermat's Little Theorem is cleaner. For composite $n$ , $\phi(n)$ precisely captures which elements participate in this multiplicative cycling.

connection

Connection to Cyclotomic Polynomials and Galois Theory: The totient function $\phi(n)$ equals the degree of the $n$ -th cyclotomic polynomial $\Phi_n(x)$ , which is the minimal polynomial of primitive $n$ -th roots of unity. Specifically, $\Phi_n(x) = \prod_{\gcd(k,n)=1, 1 \leq k \leq n} (x - e^{2\pi i k/n})$ has degree $\phi(n)$ . This connects elementary number theory to Galois theory: the Galois group of $\mathbb{Q}(\zeta_n)$ over $\mathbb{Q}$ (where $\zeta_n$ is a primitive $n$ -th root of unity) is isomorphic to $(\mathbb{Z}/n\mathbb{Z})^*$ , the multiplicative group of units modulo $n$ , which has order $\phi(n)$ . This bridge between counting coprime integers and field extensions is one of the deepest in mathematics.

Euler's Totient Function and Euler's Theorem

Euler's Totient Function and Euler's Theorem

Overview

Core Theory

Examples and Applications

Historical Development

Connections to Other Areas

What You Need First

What This Opens Up

See Also