# 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$.

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}{\left\langle #1 \right\rangle}% \newcommand{\braces}{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\down}{\downarrow}% \newcommand{\ds}{\displaystyle{#1}}% \newcommand{\equalby}{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}{\left\vert #1\right\rangle}% \newcommand{\ol}{\overline{#1}}% \newcommand{\pars}{\left( #1 \right)}% \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}}% \newcommand{\verts}{\left\vert\, #1 \,\right\vert}$ $$a + x = 3p + \delta\,,\quad x = 0, 2, 4\,,\quad p,\delta \in {\mathbb Z}\,,\quad \delta = 0,1,2$$

$$\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}$$