If $ n > 0$ and $n^2+1$ is prime, then $n=1$ or $n$ is even

1k Views Asked by At

If above exact question has been answered please provide the link. I searched but no luck.

Is the following proof correct?

(i) let $n^2+1 =2$ (2 is prime) so $n^2 = 1$ therefore $n=1$ as $n > 0$.

(ii) let $n^2+1=p$ where $p$ is prime, $p > 2$ so $p$ odd. Then $n^2 = p-1 = 2q \,\,$ ($ q \in \mathbb{Z}\,\,$) so $2 \mid n^2$ therefore n is even. Q.E.D

Also can we prove the above by contrapositive?

Here is an attempt to do so:

Math Statements: let A: If $n > 0$ and $n^2+1$ is prime; B: $n=1$ or $n$ is even.

We showed above $ A \Rightarrow B $. By contrapositive we have to show $ \lnot B \Rightarrow \lnot A\,\, $ where $\lnot A$ : $n \leq 0$ OR $n^2+1$ is not prime and $\lnot B$ : If $n \neq 1$ AND $n$ is odd.

Proof by contrapositive:

We have $n \neq 1$ and $n$ is odd then $n^2+1 \neq 2$. Let $n= 2q+1$ ($q \neq 0 $ must be). We obtain:

$n^2 +1 = (4q^2+4q+1)+1 = 2(2q^2+2q+1)$.

Therefore $n^2+1$ is even and not prime.

However this proof by contrapositive is incomplete. It shows that $n^2+1$ is not prime but if we cannot show that how can we show the other conclusion of the "OR" of $\lnot A$ i.e. that $n \leq 0$?

2

There are 2 best solutions below

2
On

I can’t comment yet so I’m writing this as an answer.

Consider $n=-1$, what then is $n^2+1$? What happens when $|n|>1$?

You proved you can’t give odd primes if $n$ is odd and not 1, but you did not check for even primes, ie: 2. Since you can partition integers by parity, this would capture every case.

0
On

It is clear if $n$ is odd then $n^2 + 1$ is even and we all know that there is only one even prime number which is '2' so for that n can be +1 or -1. After that there is no prime number which can be even. You can even relate this problem with Mersenne Prime Number formula.