Aφ(30) = 14, because you remove multiples of 2, 3, and 5 from 1–30
Bφ(30) = 8, using the formula 30 × (1 − 1/2) × (1 − 1/3) × (1 − 1/5) = 8
Cφ(30) = 12, because 30 has 3 prime factors and each contributes 4 coprime integers
Dφ(30) = 15, because exactly half of the integers up to 30 share no factor of 2
φ(30) = 30 × (1 − 1/2) × (1 − 1/3) × (1 − 1/5) = 30 × (1/2) × (2/3) × (4/5) = 8. The integers coprime to 30 in {1,...,30} are {1, 7, 11, 13, 17, 19, 23, 29} — exactly 8. The formula works by inclusion-exclusion: start with 30, remove the 15 multiples of 2, the 10 multiples of 3, the 6 multiples of 5, then add back the double-counted multiples of 6, 10, 15, subtract multiples of 30. The product formula compresses this entire inclusion-exclusion into a single expression.
Question 2 Multiple Choice
For any prime number p, φ(p) = p − 1. Why?
ABecause all even numbers less than p are not coprime to p, leaving p − 1 odd numbers
BBecause the only positive factor of a prime p is 1 and p itself, so all integers from 1 to p−1 are coprime to p
CBecause the multiplicative group mod p has exactly p − 1 generators
DBecause p − 1 is always even, ensuring the group has exactly two generators
A prime p has exactly two positive divisors: 1 and p. Therefore, gcd(k, p) = 1 for every k in {1, 2, ..., p−1} — none of these share any common factor with p. All p−1 integers below p are coprime to p, so φ(p) = p − 1. From the formula: φ(p) = p × (1 − 1/p) = p − 1. This is also why Fermat's little theorem states a^(p−1) ≡ 1 (mod p) for gcd(a,p) = 1 — the multiplicative group mod p has order p − 1.
Question 3 True / False
φ(n) equals the number of elements in the multiplicative group of integers modulo n — that is, the count of residues in {1, ..., n−1} that have multiplicative inverses mod n.
TTrue
FFalse
Answer: True
An integer k has a multiplicative inverse mod n if and only if gcd(k, n) = 1. This is exactly the condition that φ(n) counts. So φ(n) is both 'the count of integers up to n coprime to n' and 'the order of the multiplicative group (ℤ/nℤ)×'. This dual interpretation — counting coprime integers vs. measuring group size — is why φ appears in Euler's theorem: raising any element of the group to the power equal to the group's order returns the identity element 1.
Question 4 True / False
φ(mn) = φ(m)φ(n) for most positive integers m and n.
TTrue
FFalse
Answer: False
This is the multiplicativity property, but it only holds when gcd(m, n) = 1. For example, φ(4) = 2, φ(2) = 1, but 4 = 2 × 2 and gcd(2, 2) = 2 ≠ 1, so φ(4) = 2 ≠ φ(2)φ(2) = 1. The correct statement is: φ is a *multiplicative* arithmetic function, meaning φ(mn) = φ(m)φ(n) whenever gcd(m, n) = 1. This condition is essential — it is what allows you to decompose n into prime powers and compute φ separately for each.
Question 5 Short Answer
Explain why knowing φ(n) for n = pq (a product of two large primes) is computationally easy if you know p and q, but essentially impossible if you only know n — and why RSA's security depends on this.
Think about your answer, then reveal below.
Model answer: If you know p and q, then φ(pq) = (p−1)(q−1), computable in a single multiplication. But if you only know n, recovering φ(n) requires knowing p and q — which requires factoring n. Factoring the product of two large primes (each ~1000+ bits) is believed to be computationally intractable with current algorithms. RSA exploits this: n = pq is public, but φ(n) = (p−1)(q−1) is kept secret. Encryption and decryption exponents are chosen as inverses mod φ(n), and Euler's theorem guarantees that decryption undoes encryption. An attacker who cannot factor n cannot compute φ(n) and cannot find the decryption key.
The security of RSA reduces to the integer factorization problem: no efficient classical algorithm is known for factoring large semi-primes. The connection to φ is direct — knowing any one of {p, q, φ(n), d (the decryption exponent)} allows you to recover all the others efficiently. So factoring n, computing φ(n), and breaking RSA are computationally equivalent problems. This is why φ, a pure number-theoretic counting function, sits at the heart of the most widely deployed asymmetric encryption scheme.