Question

How many positive integers less than or equal to 100 are not divisible by 2, 3, or 5?

• A. 26
• B. 18
• C. 31
• D. None

Hint:

Use Inclusion-Exclusion to handle "not divisible by..." problems over multiple sets.

Answer 1

The Correct Option is A

We use the inclusion-exclusion principle. Let \( N = 100 \) Divisible by: - 2: \( \left\lfloor \frac{100}{2} \right\rfloor = 50 \) - 3: \( \left\lfloor \frac{100}{3} \right\rfloor = 33 \) - 5: \( \left\lfloor \frac{100}{5} \right\rfloor = 20 \) Pairs: - 2 and 3: \( \left\lfloor \frac{100}{6} \right\rfloor = 16 \) - 2 and 5: \( \left\lfloor \frac{100}{10} \right\rfloor = 10 \) - 3 and 5: \( \left\lfloor \frac{100}{15} \right\rfloor = 6 \) Triple: - 2,3,5: \( \left\lfloor \frac{100}{30} \right\rfloor = 3 \) Now use Inclusion-Exclusion: \[ n = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 \] So, numbers not divisible by 2, 3 or 5: \[ 100 - 74 = \boxed{26} \]