Numbers $\leq100$ not divisible by $2,3$ and $5$

Question

I am stuck here. The result should be $26$, but I am getting an incorrect result:

No.s divisible by $2= 50$
No.s divisible by $3= 33$
No.s divisible by $5= 20$
No.s divisible by $2 , 3= 14$
No.s divisible by $3 , 5= 6$
No.s divisible by $2 , 5= 10$
No.s divisible by $2, 3 , 5= 3$

Therefore, my result would be: $50+33+20-14-6-10-3=70$ Edit: Of course I meant the non-divisible numbers would be.. 30 What am I doing wrong?

1st, you're getting the numbers that are divisible, but asking for the numbers that aren't. 2nd, look at the ones divisible by 2 and 3 again. 3rd, the ones divisible by all should get the sign opposite to the ones divisible by two of the numbers. — Gerry Myerson, Jul 20 '13 at 07:48
Welcome to MSE! For some basic information about writing math at this site see e.g. here, here, here and here. — Cortizol, Jul 20 '13 at 07:51

score 5 · Answer 1 · answered Jul 20 '13 at 07:49

You made at least two mistakes, one arithmetic and one in applying the inclusion-exclusion formula. $6\cdot16=96$, so there are $16$ positive integers less than or equal to $100$ that are divisible by $2$ and by $3$. The other mistake is that you applied the wrong algebraic sign to the last term. You should have

$$50+33+20-16-6-10+3=74\;,$$

positive integers less than or equal to $100$ that are divisible by at least one of $2,3$, and $5$ and therefore $100-74=26$ that aren’t divisible by $2,3$, or $5$.

There’s a third mistake if you didn’t realize that you were counting the complement of the desired set rather than the set itself.

Stupid, stupid me for that 16*6 thing!!!!! – bookishq Jul 20 '13 at 07:55 — bookishq, Jul 20 '13 at 07:55

score 1 · Answer 2 · answered Jul 20 '13 at 08:59

Brian M. Scott's answer is fully correct; just in case the part about the "inclusion-exclusion formula" was not yet fully clear:

Visualizing this with a Venn-diagram helps (you don't necessarily need to know what a Venn-diagram is, just draw three circles):

Draw three - overlapping! - circles, one for the multiples of 2, one for the multiples of 3 and one for the multiples of 5. In a sense, you want to compute the "total area" of the union of these three circles. You start by adding the areas of the three circles (this gives 50+33+20), but then you counted the regions where two circles overlap twice. In order to fix this, you subtract these areas again (hence the -16-6-10). But then, the region where all three overlap has been added 3 times in the beginning and has been subtracted 3 times in the second step, so you add that part again (therefore +3).

Maybe this explanation was not really necessary any more, in which case I apologize.

score 1 · Answer 3 · answered Jul 20 '13 at 09:35

The other approach is that there is a Euler totient for every complete multiple of 30, so there are three full mulitiples of 30, and the numbers from 1 to 10.

So we have $3 * \phi(30) + 2 = 24 + 2 = 26$

When you do things by subtracting multiples like of 2, 3, 5 etc, you need to take account of overlaps. All of the numbers that are multiples of 10, are added in at 2, and 5, so we must remove the full set. Multiples of 30 are added in three times, and then subtracted out three times, so we need a restoring element.

    2         50      
    3      +  33      
    5      +  20    
    6      -  16      added at 2, 3,  - so subtract here
   10      -  10      added at 2, 5    so subtract one set
   15      -   6      added at 3, 5    so subtract one set
   30      +   3      added at 2, 3, 5,  subtracted with 10, 15, 30,  add one in

It gives 50+33+20+3 = 106, less 16-10-6, = 32 gives 74, of which 26 are left over.

Could you expand on the first part of your answer? Why is there a relatively prime number for every multiple of 30, and why the numbers 1-10? — Nico A, Mar 03 '19 at 17:35

Numbers $\leq100$ not divisible by $2,3$ and $5$

3 Answers3