Using inclusion-exclusion principle to count the integers in $\{1, 2, 3, \dots , 100\}$ that are not divisible by $2$, $3$ or $5$

5.5k Views Asked by At

Question: How many integers in $\{1, 2, 3, \dots , 100\}$ are not divisible by $2$, $3$ or $5$?

Can anyone give me a full explain of how this applies to the inclusion-exclusin principle? Because I got $96$ as answer, but I doubt that it is correct.

2

There are 2 best solutions below

0
On

Start with 100

Subtract 50 even numbers, 33 divisible by 3, 20 divisible by 5.

But then we need to add the numbers that we subtracted twice.

16 numbers divisible by (2*3), 10 numbers divisible by (2*5) and 6 numbers divisible by (3*5).

Then again subtract the 3 duplicates that are multiple of 2*3*5 = 30.

100 - 103 + 32 - 3 = 26.

0
On

We need to substact the $50$ multiples of 2, the $33$ multiples of $3$ and the $20$ multiples of $5$

Except now we substracted the multiple of $6$, $10$ and $15$ twice.

So we need to add $16, 10$ and $6$ back.

Except now the multiples of $30$ have been counted twice. So we substract $3$

We get $100-103+32-3=26$