$\begingroup$

I tried this problem, but I think that the way I gave a counterexample is the wrong way to prove this, because I believe I need a more general proof. How do I start to prove for ALL n > 3?

CounterExample:

Let n = 5.

Then n is prime.

2n+1 = 11.

So 2n + 1 is also prime.

4n+1 = 21.

21 is not prime.

Therefore, if n > 3 then n, 2n + 1 and 4n + 1 cannot all be prime.

$\endgroup$ 2

5 Answers

$\begingroup$

Hint $\ $ If $\,n=0\,\pmod{3}\,$ then $\,3\mid n\,$ so $n$ is not prime (by $n>3)$

Else if if $\ \color{#c00}{n\equiv 1}\pmod 3\,$ then $\,2\,\color{#c00}n+1\equiv 2\cdot\color{#c00}1 +1\equiv 0\ $ so $\ 3\mid 2n+1\,$ so $\ldots$

Else $\quad\ \ n\equiv 2\pmod3\ $ then $\ \ldots$

Remark $\ $ If congruences are unknown then they can be eliminated, yielding

Hint $ $ If $\,n = 3q+0\ $ then $\,3\mid n\,$ so $\ \ldots$

Else if $\,\ \ \color{#c00}{n = 3q+1}\,$ then $\ 2\,\color{#c00}n+1 = 2(\color{#c00}{3q+1})+1 = 3(2q+1)\ $ so $\,3\,$ divides $\,2n+1\,$ so $\ \ldots$

Else $\quad\ \color{}{n = 3q+2}\ $ then $\ \ldots$

Every integer $\,n\,$ has one of the above $\,3\,$ forms since by division $\, n = 3q+r\,$ for $\,0\le r\le 2$

$\endgroup$ 1 $\begingroup$

To prove a statement like this, you actually need to show that $n$, $2n+1$, and $4n+1$ cannot all be prime for any $n$, not just your counterexample of $n=5$.

$\endgroup$ 5 $\begingroup$

If $n$ is prime and bigger than $3$, then $n \pmod 3$ is either $1$ or $2$. Then there are two cases; one of which will lead to $2n+1$ being a multiple of $3$, and the other will lead to $4n+1$ being a multiple of $3$.

$\endgroup$ 4 $\begingroup$

In $\mathbf Z/3\mathbf Z$, $\; n(2n+1)(4n+1)\equiv n(-n+1)(n+1)=n(1-n^2)=n-n^3=0,\;$ by Lil' Fermat.

If you don't know about congruences, here a version without their explicit use: \begin{align} n(2n+1)(4n+1)&=n\bigl((3n+1)-n\bigr)\bigl((3n+1)-n\bigr)=n(3n+1)^2-n^3\\% &=(9n^3+6n^2)+n-n^3\\ &=3(3n^3+2n^2)+n(n-1)(n+1). \end{align} Now in the second term, one of $n$, $n-1$, $n+1$ is divisible by $3$, hence $3$ can be factored out from $n(2n+1)(4n+1)$.

$\endgroup$ 3 $\begingroup$

=== simpler way; inspired, but I believe significantly different enough, from other answers ========

Every third number is divisible be $3$. That is:1,2,$3$,4,5,$6$,7,8,$9$,10,....

So given $n-1, n, n+1$ one of them will be divisible by 3.

$4n -1 = n-1 + 3n$ so this is divisible by $3$ if and only if $n-1$ is divisible by $3$.

$2n - 1 = 2(n+1) - 3$ so this divisible by $3$ iff and only if $n+1$ is divisble by $3$.

So as exactly one of $n-1,n,n+1$ is divisible by $3$ then exactly one of $4n -1, n, 2n-1$ is divisible by $3$. And as $n > 3$ it follows $4n -1 > 11 > 3$ and $2n - 1 > 5 > 3$. So the number that is divisible by $3$ is not $3$ and is, therefore, not prime.

=== older way ====

It's more than just that one of them must not be prime. One of them must be divisible by 3.

Here's a thorough proof, maybe more than you need.

Mathematical fact: Given any positive integer $d$, then for any integer $m$ there will exist a unique set of of integers $q$ and $r$ so that: $m = qd + r$ and $0 \le r < k$.

One very useful way to think about this is as a division theorem: If you have an integer $m$ and you divide it by a positive integer divisor $d$, the result will be a unique integer quotient $q$ and unique remainder (which could be 0) $r$. In other words... $m = qk + r$.... for any $m$ and $k$ there are unique $q$ and $r$.

This is also called the archimedian principal and if it hasn't been already proven in your class, you can probably take is as a given fact.

So now your proof.

For any $n > 3$ we can write $n = 3q + r$ where $q$ and $r$ are unique and $r = 0, 1$ or 2.

Then $2n - 1 = 2(3q +r) = 6q + 2r - 1$ and $4n-1 = 4(3q+r) - 1= 12q +4r -1 = 3(4q +r) + r -1$.

As $n > 3$ we know $q \ge 1$.

There are three cases to consider:

Case 1: r = 0.

Then $n = 3q$ and this is not prime because $3$ divides $n > 3$ and $q | n$.

Case 2: r = 1.

Then $4n -1 = 3(4q + 1) + 1 -1 = 3(4q+1)$ and this is not prime because $3$ divides $4n -1> 3$ and $4q+1 \ge 5$ divides $4n -1$.

Case 3: r = 2.

Then $2n - 1 = 6q + 2(2) - 1 = 6q +3 = 3(2q+1)$ which is not prime because $3$ divides $2n-1 > 3$ and $2q+1 > 3$ divides $2n-1$.

Note: this proof won't work with $n = 3 = 3q + 4; q = 1; r=0$ because:

$n=3 = 3q$ but $3$ is prime and $q = 1$.

Meanwhile $2n-1$ and $4n -1$ are neither divisible by $3$ and, as it turns out, are $5$ and $11$ respectively, and both prime.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy