• 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. 1. How many numbers from 1 to 100 are divisible by 3 or 5?

    1. 53
    2. 47
    3. 46
    4. 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. 2. How many numbers from 1 to 100 are divisible by neither 2 nor 3?

    1. 17
    2. 50
    3. 34
    4. 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. 3. How many numbers from 1 to 100 are divisible by both 4 and 6?

    1. 8
    2. 6
    3. 10
    4. 25
    Show answer

    Answer: A. Such numbers are multiples of lcm(4, 6) = 12, and ⌊100/12⌋ = 8 (12, 24, ..., 96).

  4. 4. How many divisors does 360 = 2³ × 3² × 5 have?

    1. 18
    2. 20
    3. 24
    4. 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. 5. A is the set of divisors of 24 and B is the set of divisors of 36. What is n(A ∪ B)?

    1. 17
    2. 12
    3. 9
    4. 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.

Privacy · Terms · Refunds · Delivery