# 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. Oct 11, 2013 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$. Oct 11, 2013 at 14:36
• 2 is a generator of $\mathbb{Z}_3$.
– John
Oct 11, 2013 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, 2013 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. Oct 11, 2013 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. Oct 11, 2013 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. Oct 11, 2013 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. Oct 11, 2013 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. Oct 12, 2013 at 0:10

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.

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.

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$ Oct 11, 2013 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
Oct 12, 2013 at 0:23
• That's right :) Oct 12, 2013 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$$

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