How many numbers less than or equal to $120$ are divisible by $2 $, $3$ or $5$?

Question

How many numbers less than or equal to $120$ are divisible by $2 $, $3$ or $5$ ?

---

I solved it by Inclusion - Exclusion principle.

Just out of curiosity,

How can I use Euler Totient function for similar questions and even larger numbers ?

Answer 1

The integers $1\leq n\leq 120$ which are not divisible by $2,3$ or $5$ are precisely those which are relatively prime to $120$, hence there are $\phi(120)$ of them. Therefore $120-\phi(120)$ integers $1\leq n\leq 120$ are divisible by $2,3$ or $5$.

An alternate proof is to use the inclusion-exclusion principle. (This is one way of proving that the totient function is multiplicative.)

Answer 2

We can solve by using Euler's totient function as follows: We can see that 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$.

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