# How many numbers between 1 and 1000 can be divided by both $a$ and $b$

I need to find the number of natural numbers between 1 and 1000 that are divisible by 3, 5 or 7.

I know that given a set of numbers, 1 ... n, the number of numbers divisible by d is given by $\lfloor \frac{n}{d} \rfloor$

So if we let $A$ be the set of numbers divisible by 3, $B$ be the set of numbers divisible by 5 and $C$ be the set of numbers divisible by 7, then the size of the union of those sets is going to be the number required.

However, to work out $A \cup B \cup C$, I need to know $A \cap B$ (and $A \cap C$ etc).

My only thought was that to work out $A \cap B$, I could use $\lfloor \frac{1000}{3 \times 5} \rfloor$, but I am unsure if this misses out some numbers. Is that the correct way to do it or not? If no, can anyone suggest the correct way.

-

## 3 Answers

In general, you have to use $\left\lfloor\frac{1000}{[a,b]}\right\rfloor$, where $[a,b]$ is the least common multiple of $a$ and $b$.

-

That's right. A number is divisible by 3 and 5 if and only if it is divisible by 15.

-

You can be sure that it does not miss any number. It comes out as an multiplication because you are looking for the common multiple of 2 prime numbers.

It would be the same for the other intersections that you need. $$(A\cap B), (A \cap B \cap C)$$

-