- Practice
- About 15 min
- 5 practice questions
Counting with divisibility: multiples, divisors and the union formula
Count multiples, numbers divisible by neither of two numbers and common divisors by turning each into a set and using n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
If something looks wrong, please tell us.
A favourite exam setting for sets is the set of numbers divisible by something. 'How many numbers up to 100 are divisible by 3 or 5?' is a union question in disguise, and 'divisible by both' is an intersection. Once you see this, the formula n(A ∪ B) = n(A) + n(B) − n(A ∩ B) does all the work, and a little number sense gives each count.
The counting tools
- The number of multiples of k from 1 to N is the whole-number part of N ÷ k, written ⌊N/k⌋. For example there are ⌊100/7⌋ = 14 multiples of 7 up to 100.
- A number divisible by both a and b is divisible by their lcm. So A ∩ B (multiples of a and of b) is the set of multiples of lcm(a, b).
- The numbers divisible by neither a nor b are the complement of the union: N − n(A ∪ B).
- The common divisors of two numbers are exactly the divisors of their hcf.
n(multiples of a or b up to N) = ⌊N/a⌋ + ⌊N/b⌋ − ⌊N/lcm(a, b)⌋. Common divisors of two numbers = divisors of their hcf. If n = p^x q^y r^z (prime factorisation), then n has (x + 1)(y + 1)(z + 1) divisors.
Worked example 1: divisible by 3 or 5
How many numbers from 1 to 100 are divisible by 3 or 5? Let A be the multiples of 3 and B the multiples of 5. Then n(A) = ⌊100/3⌋ = 33 and n(B) = ⌊100/5⌋ = 20. A ∩ B is the multiples of 15, and ⌊100/15⌋ = 6. So n(A ∪ B) = 33 + 20 − 6 = 47. Forgetting to subtract 6 gives 53, the usual wrong answer.
Worked example 2: divisible by neither
How many numbers from 1 to 100 are divisible by neither 2 nor 3? Multiples of 2: 50. Multiples of 3: 33. Multiples of 6: ⌊100/6⌋ = 16. The union is 50 + 33 − 16 = 67. The numbers in neither set are 100 − 67 = 33. Check by pattern: in every block of 6 consecutive numbers only 2 (those leaving remainders 1 and 5) are free of 2 and 3, and 100 = 16 × 6 + 4, so we get 16 × 2 = 32 from the full blocks plus 1 more from the last four numbers 97, 98, 99, 100 (the number 97 qualifies). The total is 33.
Worked example 3: divisors of two numbers
Let A be the set of divisors of 24 and B the set of divisors of 36. A = {1, 2, 3, 4, 6, 8, 12, 24} has 8 elements and B = {1, 2, 3, 4, 6, 9, 12, 18, 36} has 9. The hcf of 24 and 36 is 12, so A ∩ B is the set of divisors of 12, namely {1, 2, 3, 4, 6, 12}, with 6 elements. Then n(A ∪ B) = 8 + 9 − 6 = 11.
Worked example 4: counting divisors from the factorisation
How many divisors does 360 have? Write 360 = 2³ × 3² × 5¹. A divisor is 2^a × 3^b × 5^c with a from 0 to 3, b from 0 to 2 and c from 0 to 1, chosen independently: 4 × 3 × 2 = 24 divisors. This is the same 'choice per factor' idea as the 2ⁿ rule for subsets. Of these, the number of divisors that are perfect squares needs even exponents: a ∈ {0, 2}, b ∈ {0, 2}, c = 0, which gives 2 × 2 × 1 = 4 (namely 1, 4, 9, 36).
Traps
- Using the product ab instead of lcm(a, b): multiples of both 4 and 6 are multiples of 12, not 24.
- Adding n(A) + n(B) and stopping: the overlap must be subtracted.
- Counting a limit that does not divide evenly: ⌊100/3⌋ is 33, not 33.33 and not 34.
- Forgetting that 1 and the number itself are divisors.
Key takeaways: turn the words into sets, use ⌊N/k⌋ for each count, use lcm for 'both' and hcf for common divisors, and take the complement for 'neither'. Check small cases by listing.
Check your understanding
-
1. How many numbers from 1 to 100 are divisible by 3 or 5?
- 53
- 47
- 46
- 38
Show answer
Answer: B. There are 33 multiples of 3, 20 multiples of 5 and 6 multiples of 15. The union has 33 + 20 − 6 = 47 numbers.
-
2. How many numbers from 1 to 100 are divisible by neither 2 nor 3?
- 17
- 50
- 34
- 33
Show answer
Answer: D. Multiples of 2: 50; of 3: 33; of 6: 16. The union is 67, so 100 − 67 = 33 numbers are in neither set.
-
3. How many numbers from 1 to 100 are divisible by both 4 and 6?
- 8
- 6
- 10
- 25
Show answer
Answer: A. Such numbers are multiples of lcm(4, 6) = 12, and ⌊100/12⌋ = 8 (12, 24, ..., 96).
-
4. How many divisors does 360 = 2³ × 3² × 5 have?
- 18
- 20
- 24
- 30
Show answer
Answer: C. The exponents can be chosen in 4 × 3 × 2 ways (0 to 3, 0 to 2, 0 to 1), which is 24.
-
5. A is the set of divisors of 24 and B is the set of divisors of 36. What is n(A ∪ B)?
- 17
- 12
- 9
- 11
Show answer
Answer: D. n(A) = 8, n(B) = 9, and A ∩ B is the set of divisors of the hcf 12, which has 6 elements. So n(A ∪ B) = 8 + 9 − 6 = 11.
Sign in to keep track of the lessons you finish.