# Primes and a polynomial

This should be easy but at this moment I have no useful idea on how to solve it and the problem is:

Show that there exist an infinite number of prime numbers that are not expressible as $p=n^2+2$.

-
The intended method depends on where in the book the question is. –  André Nicolas Jan 31 '13 at 18:50
I didn`t find the question in a book. –  A.P. Jan 31 '13 at 18:54
reciprocity is not necessary. The possible values of $n^2 \pmod 4$ are $0,1.$ So, the possible values of $n^2 +2 \pmod 4$ are $2,3,$ never 1. –  Will Jagy Jan 31 '13 at 18:58
I don't see how this follows from Bertrand's Postulate: every interval $[x,2x]$ contains an integer of the form $n^2+2$ (when $x\ge5.5$). –  Greg Martin Jan 31 '13 at 20:13
You can also use Chebyshev's lower bound for the number of primes up to $x$, which is of the form $cx/\log x$ for some positive constant $c$; when $x$ is large, this exceeds the number of integers of the form $n^2+2$ up to $x$, which is $\lfloor\sqrt{x-2}\rfloor < \sqrt x$. –  Greg Martin Jan 31 '13 at 20:15

$n^2+2\equiv 2,3 \text{ mod } 4$. There are infinitely many primes of the form $4k+1$.

-
If I were the OP, I might ask, "how do you know this"? –  Rick Decker Jan 31 '13 at 20:02
The most elementary proof I know of this: if there were finitely many such primes $p_1,\dots,p_m$, let $N=(2p_1\cdots p_m)^2+1$. Then every prime dividing $N$ must be of the form $4k+1$ (nontrivial, but elementary number theory), but none of $p_1,\dots,p_m$ can divide $N$, a contradiction. –  Greg Martin Jan 31 '13 at 20:17

For fun we give a detailed proof that does not use any material on quadratic congruences. The proof is elementary, a mild variant of Euclid's proof that there are infinitely many primes.

We want to prove that there are infinitely many primes which are not of the form $n^2+2$.

If $n^2+2$ is to be an odd prime, $n$ must be odd. And if $n$ is odd, then $n^2\equiv 1\pmod{8}$. It follows that $n^2+2\equiv 3\pmod{8}$.

So it suffices to prove that there are infinitely many primes which are not congruent to $3$ modulo $8$.

Let $b$ be any positive integer. We show that there is a prime $p\gt b$ such that $p$ is not of the form $8k+3$. Let $$N=8b! -1.$$ Note that any prime divisor $p$ of $N$ is greater than $b$. For if $p\le b$, then $p$ divides $8b!$. And if $p$ divides $8b!$ and $8b!-1$, then $p$ divides $1$, which is impossible.

We claim that $N$ has at least one prime divisor $p$ which is not of the form $8k_3$. It will follow that there must be primes $\gt b$ not of the shape $n^2+2$ beyond $b$.

It is easy to show that the product of two numbers that are congruent to $3$ modulo $8$ is congruent to $1$ modulo $8$. Thus the product of an even number of numbers all $\equiv 3\pmod{8}$ is congruent to $1$ modulo $8$, and the product of an odd number of numbers $\equiv 3\pmod{8}$ is congruent to $3$ modulo $8$.

But $N\equiv 7\pmod{8}$, so $N$ must have at least one prime divisor which is not of the form $8k+3$. This completes the proof that there are infinitely many primes which are not of the form $8k+3$.

Remark: Note that we have not shown that $N$ has no prime divisors of the form $8k+3$. That is probably in general false. But we have shown that for sure $N$ has a prime divisor which is not of that form, and that is enough to settle our problem.

-

Use quadratic reciprocity. -2 isn't a square modulo every prime.

-