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

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.

• The twin prime conjecture was not proven yet. – N. S. Oct 11 '13 at 14:08
• Can you prove that one of $n,n+1,n+2$ is divisible by $3$? Because $3\mid n+1$ if and only if $3\mid n+4$. – Thomas Andrews Oct 11 '13 at 14:36
• 2 is a generator of $\mathbb{Z}_3$. – John Oct 11 '13 at 17:39
• @Blaisorblade Sure. It ultimately boils down to $4 \equiv 1$. So regardless of which coset of $\frac{\mathbb{Z}}{3\mathbb{Z}}$ $n$ represents, $\{n, n+2, n+4\}$ is the set of all three cosets. Use the natural isomorphism between the three cosets and the modular group. You could also think of adding $n$ as merely permuting the three cosets. – John Oct 11 '13 at 18:49
• Yes there was a huge contribution to something very similar, but not directly to the twin prime conjecture. Zhang proved that there exists some $D$ so that there are infinitely many primes of the form $p, p+D$. To prove the twin prime conjecture one needs to prove that $D=2$ works, and people keep reducing the upperbound on $D$ which comes out of Zhang's proof. Zhang proved that $D$ is less than 70 million, and there is a huge difference between 70 million and 2. I think that Tao reduced the upperbound to 4680, which is huge progress, but it is not clear if the new bound can be improved. – N. S. Oct 11 '13 at 19:29

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

• It's a proof sketch, as you might find in published mathematical literature. I don't like it too much because it's asymmetric, but it certainly looks like a proof to me. – Blaisorblade Oct 11 '13 at 17:42

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

• Looks most elegant to me. – Blaisorblade Oct 11 '13 at 17:40

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

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.

• I wouldn't call it silly, but note that there's tiny typo in the sum, there's a 2 instead of a 1. I like the idea tho. – Robert Badea Oct 11 '13 at 23:56
• @RobertBadea Thanks for catching the typo. IMO it's a bit silly because this is not how most people would first think to prove this fact. Of course it works, and it generalizes pretty spectacularly when you go on to study integer-valued polynomials over the rationals (a topic related to my research), but I do think it's overkill for this problem. – user88377 Oct 12 '13 at 0:10

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.

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.

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$

• Here $n(n+2)(n+4)-n(n+1)(n+2)=n(n+2)\{(n+4)-(n+1)\}=3n(n+2)\equiv0\pmod3$ – lab bhattacharjee Oct 11 '13 at 17:10

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

• A better word would be "arbitrary", rather than "random." – Pedro Tamaroff Oct 12 '13 at 0:23
• That's right :) – DGRasines Oct 12 '13 at 0:28

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

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.

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

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

(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$$