Is φ(n) always even?

For every integer n > 2, yes — φ(n) is always even. This is because if k is coprime to n and 1 ≤ k < n, then n − k is also coprime to n, so coprime residues pair up. The only exceptions are φ(1) = 1 and φ(2) = 1.

Totient Function — Definition, Formula & Examples

The totient function, written φ(n), counts how many integers from 1 to n share no common factor with n other than 1. For example, φ(12) = 4 because exactly four numbers in {1, 2, …, 12} are coprime to 12: namely 1, 5, 7, and 11.

For a positive integer $n$ , Euler's totient function is defined as $\varphi(n) = |\{k \in \mathbb{Z} : 1 \le k \le n,\; \gcd(k, n) = 1\}|$ . Equivalently, if $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$ is the prime factorization of $n$ , then $\varphi(n) = n \prod_{i=1}^{r}\left(1 - \frac{1}{p_i}\right)$ . By convention, $\varphi(1) = 1$ .

Key Formula

\varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)

Where:

$n$ = A positive integer whose totient you want to compute
$p$ = Each distinct prime factor of n

How It Works

To compute φ(n), first find the prime factorization of n. Then apply the product formula: multiply n by the factor

(1 - 1/p)

for each distinct prime

p

dividing n. The totient function is multiplicative, meaning

\varphi(mn) = \varphi(m)\,\varphi(n)

whenever

\gcd(m,n) = 1

. This property lets you compute φ for large numbers by breaking them into coprime parts. The function appears most famously in Euler's theorem: if

\gcd(a, n) = 1

, then

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

, which generalizes Fermat's little theorem.

Worked Example

Problem: Compute φ(60).

Step 1: Find the prime factorization of 60.

60 = 2^2 \times 3 \times 5

Step 2: Identify the distinct primes dividing 60: they are 2, 3, and 5.

Step 3: Apply the product formula by multiplying 60 by (1 − 1/p) for each prime.

\varphi(60) = 60 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right)

Step 4: Evaluate each factor and multiply.

\varphi(60) = 60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 60 \cdot \frac{8}{30} = 16

Answer: φ(60) = 16. There are 16 integers between 1 and 60 that are coprime to 60.

Another Example

Problem: Use φ to find the remainder when 7^222 is divided by 10.

Step 1: Compute φ(10). Since 10 = 2 × 5, we get:

\varphi(10) = 10\left(1 - \tfrac{1}{2}\right)\left(1 - \tfrac{1}{5}\right) = 4

Step 2: Since gcd(7, 10) = 1, Euler's theorem gives us:

7^4 \equiv 1 \pmod{10}

Step 3: Write 222 = 4 × 55 + 2, so 7^222 = (7^4)^55 · 7^2.

7^{222} \equiv 1^{55} \cdot 49 \equiv 9 \pmod{10}

Answer: The remainder when 7^222 is divided by 10 is 9.

Visualization

Why It Matters

The totient function is central to the RSA cryptosystem, which secures most internet communications. Computing φ(n) when n is a product of two large primes is easy if you know the primes, but effectively impossible without them — this asymmetry is what makes RSA work. You will encounter φ(n) repeatedly in undergraduate number theory and abstract algebra courses, especially when studying group theory (the group of units modulo n has order φ(n)).

Common Mistakes

Mistake: Including 1 as a prime factor or forgetting that repeated prime factors only appear once in the product formula.

Correction: The product runs over distinct primes only. For n = 12 = 2² × 3, you use (1 − 1/2)(1 − 1/3), not (1 − 1/2)² — the exponents do not affect the number of product terms.

Mistake: Applying Euler's theorem when gcd(a, n) ≠ 1.

Correction: The theorem a^φ(n) ≡ 1 (mod n) requires that a and n be coprime. If they share a common factor, the congruence does not hold.