Soft Question- Proving a number $p$ is prime

Question

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?

It's a trick question. Find all the primes $p$ such that $p^2+8$ is also prime. — lulu, Feb 26 '19 at 11:26
@lulu Thanks, I failed to realize that :P. I think my question still stands, though. — Lt. Commander. Data, Feb 26 '19 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 '19 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 '19 at 11:29
FYI, a very similar question to prove is #16 of Northwestern U's Putnam Training Number Theory which says "If $p$ and $p^2+ 2$, are primes show that $p^3+ 2$ is prime". — John Omielan, Feb 26 '19 at 17:24

score 1 · Answer 1 · answered Feb 26 '19 at 11:36

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.

In general, considering your number modulo a "small" appropriate number can be efficient to derive some condition on it...

score 1 · Accepted Answer · answered Feb 26 '19 at 12:49

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

Soft Question- Proving a number $p$ is prime

2 Answers2