How many integers between $10000$ and $99999$, inclusive, are divisible by $3$ or $5$ or $7?$

Question

How many integers between $10000$ and $99999$, inclusive, are divisible by $3$ or $5$ or $7$?

How would I tackle these types of problems?

Answer 1

Use the inclusion-exclusion principle. Let $I=[10000,99999]$ and: $$ A = \{n\in I:n\equiv 0\pmod{3}\},$$ $$ B = \{n\in I:n\equiv 0\pmod{5}\},$$ $$ C = \{n\in I:n\equiv 0\pmod{7}\}.$$ Compute $|A|,|B|,|C|,|A\cap B|,|A\cap C|,|B\cap C|,|A\cap B\cap C|$, then recall that: $$ |A\cup B \cup C| = |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.$$ You will get something that is pretty close to $\left|I\,\right|-\left|I\,\right|\cdot\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)=\frac{19}{35}|I|.$

Answer 2

I'm willing to do a lot to avoid inclusion-exclusion, so:

$3\cdot 5\cdot 7=105$, so the pattern of multiples repeat every 105 numbers. Since you have $90000=857\cdot 105+15$ you can get the answer by taking 857 times the number of divisors in a 105-number period, plus those-among $10000, 10001, \cdots, 10014$ that are multiples of 3/5/7, which you can count by hand.

How many multiples are there in an 105-period? The non-multiples are exactly the numbers that are coprime to 105, and the number of those has a fancy name, Euler's totient function, $\varphi(105)$.

Since we know the prime factorization of $105$ (which we made just before by multiplying together some primes) it is easy to see what $\varphi(105)$ is, namely $(3-1)\cdot(5-1)\cdot(7-1)=2\cdot 4\cdot 6 = 48$. (If we don't already know this is the number of residue classes coprime to $105$ it also follows from the Chinese Remainder Theorem).

Thus the number of multiples of {3,5,7} is then $105-48=57$ so the number we're looking for is $$ 57\cdot 857 + \text{number of multiple from }10000\text{ to }10014 $$