Prove that if $a, b$ are any positive integers $>1$, then either $a$ or $b$ or $a+b$ or $a-b$ is divisible by 3.

Question

I checked all the integers from $1$ to $1000$ manually, I don't know exactly how to prove this but any simple and easy proof would be appreciated. Thanks.

Answer 1

Hint: This can be proven by induction on a, while keeping b as a constant>1. If this holds for any a>1, then by symmetry, it must hold for any b>1, while keeping a>1 a constant. Happy induction :).

Answer 2

You can prove this in a not elegant but easy way with modular arithmetic :

Suppose a and b do not divide 3

Either $a \equiv 1 [3]$ or $a \equiv 2 [3]$. You also have $b \equiv 1 [3]$ or $b \equiv 2 [3]$. Then :

if $a \equiv 1 [3]$ and $b \equiv 1 [3]$, then $a-b \equiv 0 [3]$ : a-b divide 3

if $a \equiv 1 [3]$ and $b \equiv 2 [3]$, then $a+b \equiv 0 [3]$ : a+b divide 3

if $a \equiv 2 [3]$ and $b \equiv 1 [3]$, then $a+b \equiv 0 [3]$ : a+b divide 3

if $a \equiv 2 [3]$ and $b \equiv 2 [3]$, then $a-b \equiv 0 [3]$ : a-b divide 3

Answer 3

Consider the remainder upon division by $3$ of $a$ and $b$. If it is $0$ for one of the two you are done, as $a$ or $b$ are divisible by $3$. So you are left with the options $(1,1)$, $(1,2)$, $(2,1)$ and $(2,2)$.

In the first and the last case, the difference is divisible by $3$ in the middle two, the sum.

Answer 4

Consider all integers greater than or equal to $1$, $\mathbb{N}$. Let $a\in \mathbb{N}$ be a number greater than $1$. By the Euclidean algorithm we may write $a= 3q + r$ where $r\in \{0,1,2\}$. Similarly, $b= 3s + t$ where $t\in \{0,1,2\}$.

Suppose, for a contradiction, none of the above hold (otherwise we would have the result). Fix some $b\in \mathbb{N}$ with $b\neq 1$. Since $3\nmid a$, we have $r=1$ or $r=2$. Since $3\nmid b$ we have $t=1$ or $t=2$.

If $r=1$ and $t=1$ we have $a-b=(3q+1)-(3s+1)=3q-3s=3(q-s)$ and thus $3|a-b$.

I'll let you continue for the cases $r=1$, $t=2$ and $r=2$, $t=2$ and then conclude the result by symmetry.

Answer 5

Let $a\equiv x\pmod 3$ and $b\equiv y\pmod 3$, where $x,y\in\{0,1,2\}$. Suppose, $3\nmid a$ and $3\nmid b$. So $a,b\not\equiv 0\pmod 3$ If $a\equiv b\pmod 3$, then $3|a-b$, otherwise $a\equiv 1\pmod 3$ and $b\equiv 2\pmod 3$ or vice versa. In either case $a+b\equiv 0\pmod 3$. So, $3|a+b$.

Answer 6

Hint $\,\ ab(a\!-\!b)(a\!+\!b) =\, a^3b-ab^3 =\, (\color{#c00}{a^3\!-\!a})b-a(\color{#c00}{b^3\!-\!b})$

But $\ 3\mid \color{#c00}{x^3\!-x} = (x\!-\!1)x(x\!+\!1)\,$ by $3$ divides one of three successive integers (or use little fermat)

Alternatively $\ {\rm mod}\ 3\!:\ a,b\not\equiv 0\,\Rightarrow\,a,b\equiv \pm1\,\Rightarrow\,a^2\equiv b^2\,\Rightarrow\,3\mid (a\!-\!b)(a\!+\!b)\,\Rightarrow\, 3\mid\,\ldots$

Answer 7

Consider $(a\bmod 3)$ and $(b \bmod 3)$. There are 3 possibilities for each, 9 combinations in total, which meet the possible criteria as follows:

$$\begin{array}{c|c|c} \frac{a \bmod 3 \to}{b \bmod 3} & 0 & 1 & 2 \\[0.5em] \hline 0 & \text{all} & b & b \\[0.5em] \hline 1 & a & a-b & a+b \\[0.5em] \hline 2 & a & a+b & a-b\\[0.5em] \end{array}$$

Answer 8

If $a$ or $b$ are divisible by $3$ you are done. Otherwise there are two cases:

If they have the same remainder when divided by $3$ then $a-b$ is divisible by $3$.

If they have different remainders these must be $1$ and $2$ in some order so that $a+b$ has remainder $3$ on division by $3$, so is a multiple of $3$.

Answer 9

What is the relation of $a$ to its nearest multiple of 3? What is the relation of $b$ to its nearest multiple of 3? If you think of the problem this way, the infinitely many possibilities boil down to just a few scenarios. Here $m$ and $n$ are both integers.

• If either $a = 3m$ or $b = 3n$, or both, you don't need to do anything else, you're done.
• If $a = 3m + 1$ and $b = 3n + 1$, then $a - b = (3m + 1) - (3n + 1) = 3m - 3n = 3(m - n)$.
• If $a = 3m + 2$ and $b = 3n + 2$, then $a - b = (3m + 2) - (3n + 2) = 3m - 3n = 3(m - n)$.
• If $a = 3m + 1$ and $b = 3n + 2$, then $a + b = (3m + 1) + (3n + 2) = 3m + 3n + 3 = 3(m + n + 1)$.
• If $a = 3m + 2$ and $b = 3n + 1$, then... you can figure this one out yourself.