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$.
- Prime numbers divide an element from a set
- Prove if $56x = 65y$ then $x + y$ is divisible by $11$
- Prove for positive integers a,b,c and d (where b does not equal d), if gcd(a,b) = gcd(c,d) = 1, then a/b + c/d is not an integer
- Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$
- For any prime $p > 3$, why is $p^2-1$ always divisible by 24?
- Does dividing by zero ever make sense?
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.
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$.
$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.
$$
\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}
$$
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.
By the Euclidean algorithm, one of three cases must hold:
$n=3k$, for some integer $k$
$n=3k+1$, for some integer $k$
$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$.
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$
$\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:
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.
$$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$
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.
$\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)$
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$$