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 ?
[Math] How many numbers less than or equal to $120$ are divisible by $2 $, $3$ or $5$
combinationscombinatoricspermutations
Best Answer
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.)