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$. 
 A: $n^2+2\equiv 2,3 \text{ mod } 4$. There are infinitely many primes of the form $4k+1$.
A: 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. 
A: Use quadratic reciprocity. -2 isn't a square modulo every prime.
