# Soft Question- Proving a number $p$ is prime [duplicate]

I am a high school student currently self-studying number theory using the book Elementary Number Theory by David Burton. Currently, I'm doing Chapter 3: Primes and their Distribution. I've noticed that often time the questions which come up are in this form-

If [condition], then prove that $$p$$ is prime.

This is a very general question, but in essence what I'm asking is what condition do you prove a certain number to fulfil so you can say that it's prime? For example, in the case of divisibility, we often use the argument that $$a | 1$$ to prove that $$a=1$$ and other general tricks like that.

For instance, in this question-

If $$p$$ and $$p^2+8$$ are both prime, then prove that $$p^3+4$$ is also prime.

Here I'm unable to even begin proving the question not because I don't know what to do, but because I'm unaware what kind of argument I need to use to prove a number is prime.

Is there some general argument that we often apply if we want to prove that a number is prime?

## marked as duplicate by lulu, Lord Shark the Unknown, GNUSupporter 8964民主女神 地下教會, Delta-u, José Carlos SantosFeb 28 at 13:27

• It's a trick question. Find all the primes $p$ such that $p^2+8$ is also prime. – lulu Feb 26 at 11:26
• @lulu Thanks, I failed to realize that :P. I think my question still stands, though. – Naman Kumar Feb 26 at 11:28
• Keep in mind: finding large primes is hard. If this exercise is true, finidibg large primes would be very easy. – JavaMan Feb 26 at 11:28
• To the general question: not really. It can be extremely difficult to determine if a general number is prime. – lulu Feb 26 at 11:29
• en.wikipedia.org/wiki/Primality_certificate – bof Feb 26 at 11:34

To answer your more general question, there are several ways one might do so, and it depends on context. I would say that one of the most common ways is a proof by contradiction: assume $$p$$ were not prime, then there exists a $$d>1$$ with $$d\mid p$$. Then, we try to deduce properties using $$d$$ that eventually contradicts either the condition of the problem or one of the assumptions $$d>1,d\mid p$$. Another way can be to use certain theorems so that the conditions of the problem fit nicely to give you the desired result; an obvious example is of course Wilson's Theorem, which states that a positive integer $$p$$ is prime iff $$(p-1)!=-1$$ mod $$p$$.
Let's look at that modulo $$3$$.
If $$p=0$$ mod $$3$$, and $$p \neq 3$$, then $$p$$ is not prime. If $$p=1$$ mod $$3$$, then $$p^2 + 8 = 0$$ mod $$3$$ (and $$\neq 3$$) so it is not prime. If $$p=2$$ mod $$3$$, then $$p^2 + 8 = 0$$ mod $$3$$ (and $$\neq 3$$) so it is not prime.
So the only possibility to have $$p$$ and $$p^2 +8$$ prime is that $$p=3$$.
In that case, $$p^3 + 4 = 31$$ is also prime.