Prove for any integer $a$, one of the integers $a$, $a+2$, $a+4$ is divisible by $3$. [duplicate]

Prove for any integer $a$, one of the integers $a$, $a+2$, $a+4$ is divisible by $3$.

I know I would use the division algorithm but I am really confused how to go about this. Step by step explanation please? thank you so much!

• Each number leaves a remainder of either $0$, $1$, or $2$ when divisible by $3$, according to the division algorithm. Convince yourself that no two of them are the same, and think about Pigeonhole. – user61527 Feb 11 '14 at 22:46

For every number $a$: $a \equiv {0, 1, 2} \pmod{3}$

In the first case: $a \equiv 0 \pmod{3}$

For the second one: $a \equiv 1 \pmod{3}$ => $a+2 \equiv 3 \pmod{3} \equiv 0 \pmod{3}$

For the third one: $a \equiv 2 \pmod{3}$ => $a+4 \equiv 6 \pmod{3} \equiv 0 \pmod{3}$

HInt $\, 3\mid a\!\iff\! 3\mid a\!+\!3\,$ and $\,a\!+\!2,a\!+\!3,a\!+\!4\,$ are $3$ consecutive integers, so $3$ divides one of them.

Try working modulo 3:

So we have:

$$a \equiv a \pmod 3$$ $$a + 2 \equiv a-1 \pmod 3$$ $$a + 4 \equiv a+1 \pmod 3$$

So those three numbers have same remainder when divided by 3 as $a, a+1, a-1$ and we know that exactly one of 3 consecutive number is divisible by 3.

$a$ is either odd or even. Write $a=2k$ in the first case. Then we are looking at $\{2k, 2(k+1), 2(k+2)\}$. And we know that any three consecutive integers has an integer divisible by three, thus so do this set.

In the second case write $a=2k+1$. Then we are looking at $\{2k+1, 2k+3, 2k+5\}$. This is the same as $\{2(k-1)+3, 2k+3$, and $2(k+1)+3\}$. Likewise one of $\{k-1, k, k+1\}$ is divisible by three. Thus when you multiply by two and add 3 to that one element you still have something divisible by three.

You really only have to check the three possible cases for $a$. (Normally I wouldn't suggest this "proof by exhaustion", but this problem is simple enough.)

Case I: $\displaystyle a \equiv 0 (\mod 3)$

$a$ is divisible by $3$, problem solved.

Case II: $\displaystyle a \equiv 1 (\mod 3)$

$\displaystyle a+2 \equiv 1+2 \equiv 3 \equiv 0 (\mod 3)$, and $a+2$ is divisible by $3$.

Case III: $\displaystyle a \equiv 2 (\mod 3)$

$\displaystyle a+4 \equiv 2+4 \equiv 6 \equiv 0 (\mod 3)$, and $a+4$ is divisible by $3$.


$$\begin{array}{} \delta = 0 & \imp & x = 0\,, & 3 | a \\ \delta = 1 & \imp & x = 4\,, & 3 | \pars{a + 4} \\ \delta = 2 & \imp & x = 2\,, & 3 | \pars{a + 2} \end{array}$$