Questions: Euler's Totient Function

Question 1

What is φ(12)?

• A. 2
• B. 4
• C. 6
• D. 10

Answer: (B)

Using the product formula: 12 = 2² · 3, so φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 12 · 1/2 · 2/3 = 4. You can verify by listing: of the integers 1–11, only 1, 5, 7, and 11 share no factor with 12. A common error is φ(12) = 6 (confusing with φ(9) or forgetting that multiples of both 2 and 3 are excluded), but the product formula handles this systematically.

Question 2

For a prime p, what is φ(p²)?

• A. p − 1
• B. p² − 1
• C. p(p − 1)
• D. p²

Answer: (C)

Using the product formula: φ(p²) = p² · (1 − 1/p) = p² − p = p(p − 1). Alternatively, the integers from 1 to p² that are NOT coprime to p² are exactly the multiples of p: p, 2p, 3p, …, p·p — there are p of them, leaving p² − p. Option A, p − 1, is φ(p), not φ(p²); a common confusion between the prime and its square. The multiplicativity formula φ(p^k) = p^k − p^(k−1) generalizes this.

Question 3

The formula φ(mn) = φ(m) · φ(n) holds for most positive integers m and n.

• T. True
• F. False

Answer: False

The multiplicativity formula φ(mn) = φ(m)φ(n) only holds when gcd(m, n) = 1. For example, φ(4) = 2 and φ(2) = 1, but 4 = 2 · 2 and gcd(2,2) = 2 ≠ 1, so φ(4) ≠ φ(2)φ(2) = 1. Correctly, φ(4) = 2. This condition is essential: φ is a multiplicative function in the number-theoretic sense, meaning multiplicativity holds only for coprime inputs.

Question 4

The integers from 1 to n that are coprime to n are exactly the invertible elements (units) of the ring ℤ/nℤ.

• T. True
• F. False

Answer: True

An integer a has a multiplicative inverse mod n — i.e., there exists b with ab ≡ 1 (mod n) — if and only if gcd(a, n) = 1. So the coprime residues are precisely the units of ℤ/nℤ, and φ(n) is the size of the multiplicative group (ℤ/nℤ)×. This is why φ(n) appears in Euler's theorem: a^φ(n) ≡ 1 (mod n) for gcd(a,n) = 1 is simply the statement that every unit has order dividing the group size.

Question 5

Why does Euler's theorem require gcd(a, n) = 1? What goes wrong — concretely — if a and n share a common factor?

Model answer: If gcd(a, n) = d > 1, then a is not a unit in ℤ/nℤ — it has no multiplicative inverse. Powers of a mod n cannot cycle back to 1 because a unit multiplied by a non-unit never yields a unit. For example, a = 2, n = 4: powers of 2 mod 4 are 2, 0, 0, 0, … — they never reach 1. The group structure underlying Euler's theorem applies only to the units (ℤ/nℤ)×, and a ∉ (ℤ/nℤ)× when gcd(a,n) > 1.

This condition is not just a technical nicety — it is the heart of why RSA works. In RSA, messages are encoded as integers a with gcd(a, n) = 1 (guaranteed by choosing large prime factors). Encryption raises a to an exponent e, and decryption uses Euler's theorem to find the inverse exponent d such that ed ≡ 1 (mod φ(n)), recovering a. If a shared a factor with n, the cycle structure breaks and decryption fails — which is also why RSA keys use large primes, making such collisions astronomically unlikely.