Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

13 Answers 13

up vote 23 down vote accepted

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

share|cite|improve this answer
In my opinion this is not mathematical proof! – Cristi Oct 11 '13 at 17:39
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.

share|cite|improve this answer
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} $$

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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.
share|cite|improve this answer

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$

share|cite|improve this answer
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}$.

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.


share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Suppose that n is not divisible by 3.

It means :

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


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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.