How can I prove that one of $n$, $n+2$, and $n+4$ must be divisible by three, for any $n\in\mathbb{N}$

Question

Intuitively it's true, but I just can't think of how to say it "properly".

Take for example, my answer to the following question:

Let $p$ denote an odd prime. It is conjectured that there are infinitely many twin primes $p$, $p+2$. Prove that the only prime triple $p$, $p+2$, $p+4$ is the triple $3,\ 5,\ 7$.

And my solution:

Given an odd integer $n$, between the three integers $n$, $n+2$ and $n+4$, one of them must be divisible by $3$... Three possible cases are $n=3k$, $n+2=3k$, and $n+4=3k$. The only such possible $k$ that makes $n$ prime is $k=1$. In this case, given an odd prime $p$, either $p=3$, $p+2=3$, or $p+4=3$. This would imply that $p=3$, $p=1$, or $p=-1$. The only of these three that is prime is $p=3$, therefore the only three evenly distributed primes are $3$, $5$, and $7$.

Is there a "better" way that I can assert that one of the integers is divisible by 3? This feels too weak.

Answer 1

If $n$ is divisible by $3$ there is nothing more to prove. Suppose that $n$ is not divisible by $3$ Then the remainder of dividing $n$ by $3$ is either $1$ or $2$. In the first case $n + 2$ is divisible by $3$; in the second case $n + 4$ is divisible by $3$.

Answer 2

$n+4$ is divisible by 3 if and only if $n+1$ is, so it's enough to consider the three consecutive numbers $n$, $n+1$ and $n+2$, one of which is divisible by 3.

Answer 3

A somewhat silly answer:

You probably know that $\displaystyle \sum_{i=1}^n i = \frac{n(n+1)}{2}$ and $\displaystyle \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$; if not these can be proven easily via induction. Consider then \begin{align*} \sum_{i=1}^n (i^2 + 3i + 1) &= \frac{n(n+1)(2n+1)}{6} + 3\frac{n(n+1)}{2} + n \\ &= \frac{(2n^3 + 3n^2 + n) + 9(n^2+n) + 6n}{6} \\ &= \frac{2n^3 +12 n^2 + 16 n}{6} \\ &= \frac{n^3 + 6n^2 + 8n}{3} \\ &= \frac{n(n+2)(n+4)}{3} \end{align*}

On the left hand side, you have a sum of integers, so the right hand side is an integer. Hence $3 | n(n+2)(n+4)$, and since $3$ is prime it divides one of the three factors.

Answer 4

$$ \begin{array}{c|lcr} n & \ n & \ n+2 & \ n+4 \\ \hline 3k & \fbox{$3k$} & 3k+2 & 3(k+1)+1 \\ 3k+1 & 3k+1 & \fbox{$3(k+1)$} & 3(k+1)+2 \\ 3k+2 & 3k+2 & 3(k+1)+1 & \fbox{$3(k+2)$} \\ \end{array} $$

Answer 5

Consider $n \mod 3$ the answer is either $0,1$ or $2$.

• If it's zero we're done and $n$ is divisible by 3.
• If it's $1$ then consider $(n+2) \mod 3 = ((n\mod3)+2) \mod 3 = 1+2\mod 3 = 0$ so $n+2$ is divisible by $3$.
• If $n\mod 3= 2$ then consider $(n+4)$ giving; $(n+4)\mod 3 = ((n\mod 3)+4)\mod3 = 2+4\mod 3 = 6\mod3 $ which is $0$ thus $n+4$ is divisible by three.

Answer 6

By the Euclidean algorithm, one of three cases must hold:

1. $n=3k$, for some integer $k$

2. $n=3k+1$, for some integer $k$

3. $n=3k+2$, for some integer $k$

Follow cases 2,3 forward to $n+2, n+4$ and you will be pleased with the result.

Answer 7

As the product of $3$ consecutive integer is divisible by $3$ (Proof)

$\displaystyle\implies 3|n(n+1)(n+2)$

Now, $n(n+r)(n+2r)-n(n+1)(n+2)\equiv2n(r^2-1)\pmod3$ which will be divisible by $3$ for all integer $n$ if $r^2\equiv1\pmod3\implies r\equiv\pm1\pmod3$

Subsequently, $n(n+r)(n+2r)\equiv n(n+1)(n+2)\pmod3\equiv0$ if $r\equiv\pm1\pmod3$

Answer 8

$\left\{ {3k/k \in \mathbb{N}}\right\}\cup\left\{ {3k+1/k \in \mathbb{N}}\right\}\cup\left\{ {3k+2/k \in \mathbb{N}}\right\}$ is a partition of $\mathbb{N}$, so for an arbitrary number $n \in \mathbb{N}$ you know that one and only one of the following cases is true:

$n=3k$, and we are done.

$n=3k+1$, then, $n+2=3k+1+2=3(k+1)$

$n=3k+2$, then, $n+4=3k+2+4=3(k+2)$

Answer 9

$\left\{3k,k\in\mathbb{N}\right\}\cup\left\{3k+1,k\in\mathbb{N}\right\}\cup\left\{3k+2,k\in\mathbb{N}\right\}$ is a partition of $\mathbb{N}$.

This means: $n$ could be only one of this form:

1. $n=3k$, for some integer $k$
2. $n=3k+1$, for some integer $k$
3. $n=3k+2$, for some integer $k$

Case 1. is clear: $n=3k$ is divisible by 3, so nothing more to prove.

Case 2. either $3k+1, 3k+1 + 2$ or $3k+1 + 4$ should be divisible by 3. But $3k + 1 + 2 = 3*(k + 1)$ which is divisible by 3.

Case 3. either $3k+2, 3k+2 + 2$ or $3k+2 + 4$ should be divisible by 3. But $3k + 2 + 4 = 3*(k + 2)$ which is divisible by 3.

Done.

Answer 10

There are other more rigorous answers already, but intuitively:

If $n$ is odd, then $n$ or $n+2$ is divisible by $3$ since they are consecutive odd numbers and every other odd number is divisible by $3$.

If $n$ is even, then $n=2k$ for some $k\in\mathbb{N}$. From this, we can recognize that $n,n+2,n+4$ correspond to $2(k),2(k+1),2(k+2)$ for some $k\in\mathbb{N}$. Since $k,k+1,k+2$ represent three consecutive natural numbers then we know that at least one of them must be divisible by $3$, and any number that is divisible by three is also divisible by three once doubled, so one of $n,n+2,n+4$ must be divisible as well.

Answer 11

$$n(n+r)(n+2r)=n(n^2+3nr+2r^2)=n^3+3n^2r+2nr^2\equiv n(n^2-r^2)\pmod3$$

If $3|n$ we are done.

Else $n\equiv\pm1\pmod3\implies n^2\equiv1\pmod3$

So, we need $r^2\equiv1\pmod3$ to make $n^2\equiv r^2\pmod3$

$\displaystyle \implies r\equiv\pm1\pmod3$

$\displaystyle \implies 3|n(n+r)(n+2r)$ if $(r,3)=1$

Answer 12

Suppose that n is not divisible by 3.

It means :

n % 3 = {1,2} let call it x

and

n + 2 % 3 = (x + 2) % 3

and n + 4 % 3 = (x + 4) % 3

So if x = 1

n + 2 % 3 = 3 % 3 = 0

n + 4 % 3 = 5 % 3 = 2

n + 2 is divisible by 3

n + 4 is not divisible by 3

else if x = 2

n + 2 % 3 = 4 % 3 = 1

n + 4 % 3 = 6 % 3 = 0

n + 2 is not divisible by 3

n + 4 is divisible by 3

Answer 13

(All congruences modulo $3$.) First, $n$ is congruent to $0$, $1$, or $-1$. The addends $0$, $2$, $4$ are congruent respectively to $0$, $-1$, $1$, one of which (call it $a$) is congruent to $-n$. Thus, $$n+a \equiv n-n \equiv 0 \mod 3$$

Answer 14

How about trying mathematical induction on $n$: For $n=1$ we have 1,3 and 5 in which 3 is divisible by 3. So result is true for $n=1$. Suppose result is true for $n=k$. Now we have to prove that result is true for $n=k+1$. We have three cases Case (1): $k$ is divisible by 3 Then $(k+1)+2=k+3$ will be divisible by 3 Case (2): $k+2$ is divisible by 3 Then $(k+1)+4=k+2+3$ will be divisible by 3 Case (3):$ k+4$ is divisible by 3 Then $k+1=(k+4)-3$ will be divisible by 3. So the result is true for $n=k+1$ hence by the Principle of Mathematical Induction ther result is true for all $n\in \mathbb N$