If p is prime and $p > 2$, then $p^2+4$ is prime.

Question

So, I'm having a bit of trouble with this proof.

That is: If $p$ is prime and $p > 2$, then $p^2+4$ is prime.

I've tried proving this by finding the contrapositve of the equivalent:

($p$ is prime $\land$ p>2) $\rightarrow (p^2+4$ is prime)

as: $\neg (p^2+4$ is prime) $\rightarrow \neg (p$ is prime $\land$ $p>2$)

So, I was thinking that if $p>2$ then the only way $p^2+4$ is not prime is if it's an even number. Then finding for $p$ in $p^2+4 = 2k$ would be:

$p = \sqrt{2k-4}$

$p = \sqrt{\frac{1}{4}(8k-16)}$

$p = \frac{1}{2} \sqrt{8k-16}$

$p = 2(\frac{1}{4}\sqrt{8k-16})$

But this seems like a stretch... Though, I suppose that if I can prove the negation of the predicate to be true then I'll be able to prove this, but I'm not sure how to go about doing so. Since, I'm unsure how to prove this directly.

Answer 1

There are infinitely many counterexamples by Dirichlet's theorem. First of all, there are infinitely many primes $p$ satisfying $p\equiv 1\bmod 5$. Then ... well, we only need some counterexamples here. So let's take some new ones $$ 31^2+4=5\cdot 193, \quad 41^2+4=5\cdot 337, \quad61^2+4=5^2\cdot 149 $$

Answer 2

You cannot prove it, since it is false: $11^2+4=125$, which is not prime. Also, $19^2+4=5\times73$, $23^2+4=13\times41$, …

Answer 3

Here is a problem you might be asked to solve in a math course:

Is the following statement true or false:

If p is prime and $p > 2$, then $p^2+4$ is prime.

We want to put the truth value on the left or right side of the following

$\tag 1 (\forall \text{ odd prime } p)\, [p^2 + 4 \text{ is a prime}] \; \text{ XOR } \; (\exists \text{ odd prime } p) \, [p^2 + 4 \text{ is not a prime}]$

The easiest way to start is to examine the $\text{rhs}$ and see where it leads.

If ${\displaystyle a_{m}a_{m-1}\ldots a_{0}}$ is the decimal representation of an integer $n$ we let $\mu(n) = a_{0}$ (the units digit).

If $p$ is an odd prime number then $\mu(p) \in \{1,3,7,9\}$.

The units digit of $p^2$ is given by the following

$\quad \mu(p) = 1 \implies \mu(p^2) = 1$
$\quad \mu(p) = 3 \implies \mu(p^2) = 9$
$\quad \mu(p) = 7 \implies \mu(p^2) = 9$
$\quad \mu(p) = 9 \implies \mu(p^2) = 1$

We can then also write as true

$\quad \mu(p) = 1 \implies \mu(p^2+4) = 5$
$\quad \mu(p) = 3 \implies \mu(p^2+4) = 3$
$\quad \mu(p) = 7 \implies \mu(p^2+4) = 3$
$\quad \mu(p) = 9 \implies \mu(p^2+4) = 5$

So if a prime number ends in either $1$ or $9$ then we know that $p^2 + 4$ is not a prime number.