0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.