Take the 2-minute tour ×
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.

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

share|improve this question
1  
The intended method depends on where in the book the question is. –  André Nicolas Jan 31 '13 at 18:50
1  
I didn`t find the question in a book. –  A.P. Jan 31 '13 at 18:54
5  
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
If I were the OP, I might ask, "how do you know this"? –  Rick Decker Jan 31 '13 at 20:02
1  
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

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.