Prime Numbers • Topic 3 of 3

Co-primes

Two numbers are co-prime (relatively prime) when their HCF is 1 — they share no prime factor. They need not be prime themselves: 8 and 9 are co-prime, though neither is prime. Co-primality drives the rule φ(mn) = φ(m)φ(n) for co-prime m, n, and it is the condition that lets the Chinese Remainder Theorem combine moduli. Euler’s totient φ(N) counts how many integers from 1 to N are co-prime to N, using φ(N) = N × ∏(1 − 1/p) over the distinct primes p of N. For a prime, φ(p) = p − 1; for a prime power, φ(p^k) = p^k − p^(k−1). Twin primes are pairs of primes differing by 2 (11 and 13, 17 and 19); any two distinct primes are automatically co-prime. In CAT, totient turns up when counting fractions in lowest terms or numbers coprime to N in a range.

✅ Solved examples

1. Find φ(36).
36 = 2² × 3². φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × ½ × ⅔ = 12.
2. How many numbers from 1 to 30 are co-prime to 30?
30 = 2 × 3 × 5. φ(30) = 30 × ½ × ⅔ × ⅘ = 8.
3. Are 15 and 28 co-prime?
15 = 3 × 5, 28 = 2² × 7. No shared prime factor ⇒ HCF = 1 ⇒ yes, co-prime (even though neither is prime).
4. How many fractions n/45 with 1 ≤ n ≤ 45 are already in lowest terms?
Lowest terms ⇔ n co-prime to 45 = 3² × 5. φ(45) = 45 × ⅔ × ⅘ = 24.

✏️ Practice — try these, take hints as needed

1. Compute φ(100).
100 = 2² × 5².
φ = 100 × (1 − 1/2)(1 − 1/5).
100 × ½ × ⅘.
40
2. How many integers from 1 to 20 are co-prime to 20?
20 = 2² × 5.
φ(20) = 20 × ½ × ⅘.
Simplify.
8
3. Are 24 and 35 co-prime?
24 = 2³ × 3, 35 = 5 × 7.
Look for a shared prime.
There is none.
Yes (HCF = 1)
4. Find φ(7) + φ(11).
For a prime p, φ(p) = p − 1.
φ(7) = 6, φ(11) = 10.
Add them.
16
5. List the twin-prime pairs below 20.
Twin primes differ by 2.
Check (3,5),(5,7),(11,13),(17,19).
All four qualify.
(3,5), (5,7), (11,13), (17,19)

📝 Topic test — 8 questions

Auto-graded with full solutions; saved to your dashboard. Use the calculator and formula sheet (top-right) any time.

Loading questions…
← Prime Factorization Take the chapter test →