2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Arthur Apr 15 '13 at 22:17
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.