# Numbers that are divisible

So I am given the following question: For natural numbers less than or equal to 120, how many are divisible by 2, 3, or 5? I solved it by inclusion-exclusion principle and by using the least common multiple by having it as (2, 3, 5)=120 which is equal to 30. Are these the right way to solve them or is there other ways?

• Hint: The probability that a random number in the given range is divisible by $2$ is $50\%$. Also, the three events "a random number in the range is divisible by $2$", "a random number in the range is divisible by $3$" and "a random number in the range is divisible by $5$" are independent. – Arthur Apr 15 '13 at 22:17

It is a right way. Inevitably there are others. For example, there are $\varphi(120)$ numbers in the interval $[1,120]$ which are relatively prime to $120$. Here $\varphi$ is the Euler $\varphi$-function.

The numbers in our interval which are divisible by $2$, $3$, or $5$ are precisely the numbers in our interval which are not relatively prime to $120$.

So $120-\varphi(120)$ gives the desired count. Compute $\varphi(120)$ by using the usual formula, and the fact that $120=2^3\cdot 3\cdot 5$.

The Inclusion/Exclusion procedure is more versatile than the Euler $\phi$-function procedure.

Inclusion-exclusion is a good choice (and I expect your teacher intended you to use this method).

However, in mathematics, there are often many methods you can use. For instance, we could instead find the answer computationally (in GAP this can be found by Number([1..120],i->i mod 2=0 or i mod 3=0 or i mod 5=0);).

There is no "best" method. In fact, it's usually best to use multiple methods in order to perform cross-checking.