Lesson 2: Inclusion–exclusion for overlapping sets
Integers divisible by 2, 3 or 5
SkillInclusion–exclusion
Worked example
How many integers from 1 to 1000 inclusive are divisible by 2, 3 or 5? Hence find how many are divisible by none of 2, 3 and 5.
Step 1: Define the sets
Let , and be the integers from 1 to 1000 that are divisible by 2, 3 and 5 respectively. We want .
Step 2: Count each set
The number of multiples of up to 1000 is the whole-number part of , so , and .
The multiples of 3 are , so there are 333 of them. Do not round up.
Step 3: Count the pair overlaps
Divisible by 2 and 3 means divisible by 6, and so on: (multiples of 6), (multiples of 10) and (multiples of 15).
2, 3 and 5 are prime, so a number divisible by two of them is divisible by their product.
Step 4: Count the triple overlap
, the multiples of 30 (since ).
Step 5: Apply inclusion–exclusion
Step 6: Take the complement
integers are divisible by none of 2, 3 and 5.
Answer
734 integers from 1 to 1000 are divisible by 2, 3 or 5, and 266 are divisible by none of them.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Define one set for each condition.
Count each set and each intersection (an intersection of "divisible by" sets is "divisible by the lowest common multiple").
Add the singles, subtract the pairs, add back the triple.
"None" is the total minus the union.
Watch out for
Rounding up to 334: there are only 333 multiples of 3 up to 1000.
Forgetting to add back , which gives 701.
For divisors that share a factor, such as 4 and 6, the overlap is the multiples of the lowest common multiple (12), not of the product (24).