3

I'm having trouble determining this problem.

I need to find the integers in the set {1, ... , 100} that are divisible by 2 or 3 but not both.

The way I tried to approach it was:

If a number is divisible by both 2 and 3 then we can say it is divisible by 6. So we need to exclude integers divisible by 6. From here am I supposed to just go through each integer? Or is there a better way to approach this?

Thanks

Pandamonium
  • 975
  • Do you know all the prime numbers between 1 and 100? – DiegoMath Sep 17 '14 at 23:21
  • 1
    Are you asking how many, perhaps? Then the answer would be $\floor(100/2) + \floor(100/3) - 2\cdot \floor(100/6) = 50 + 33 - 2\cdot 16 = 51$. You could check this by noting that $4$ in every $6$ numbers are divisible by $2$ or $3$. Then the number is $2/3\cdot 96 + 3 = 67$. Then we substract the $16$ numbers divisible by $6$. Indeed, $67- 16 = 51$ as desired. – Christopher K Sep 17 '14 at 23:32

2 Answers2

1

Every integer can be written in the form $n=6q+r$ by a division by $6$ ($r$ is the remainder of the division). The term $6q$ is a multiple of both $2$ and $3$, so it suffices to reason on the divisibility of the remainder.

The remainders are periodic,

$$\color{blue}{1,2,3,4,5,0},1,2,3,4,5,0,\color{blue}{1,2,3,4,5,0},1,2,3,4,5,0,\color{blue}{1,2,3,4,5,0,}\cdots$$

The then truth values of the condition "divisible by 2 or 3 but not both" are

$$\color{blue}{f,t,t,t,f,f,}f,t,t,t,f,f,\color{blue}{f,t,t,t,f,f,}f,t,t,t,f,f,\color{blue}{f,t,t,t,f,f,}\dots$$

You can summarize by saying, "skip $1$, then repeatedly take $3$ and skip $3$".

1

Hint: In the set $\{1,\cdots, 100\}$, count the number of multiples of $2$. Then count the number of multiples of $3$, and add the two numbers together. Then subtract twice the number of multiples of $6$. Note that the number of multiples of $6$ is $\lfloor 100/6 \rfloor = 16$, since they are: \begin{align*} 6(1) &= 6, \\ 6(2) &= 12, \\ &~~\vdots \\ 6(16) &= 96 \end{align*}

Adriano
  • 41,576