# If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....

• Math100

#### Math100

Homework Statement
If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that ## p^{3}+4 ## is also prime.
Relevant Equations
None.
Proof:

Suppose ## p ## and ## p^{2}+8 ## are both prime numbers.
Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##.
Let ## p>3 ##.
Then ## p^{2}\equiv 1 \mod 3 ##,
so ## p^{2}+8\equiv 0 \mod 3 ##.
Note that ## p^{2}+8 ## can only be prime for ## p=3 ##.
Thus ## p^{3}+4=27+4=31 ##, which is also prime.
Therefore, if ## p ## and ## p^{2}+8 ## are both prime numbers,
then ## p^{3}+4 ## is also prime.

Last edited:

Homework Statement:: If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that ## p^{3}+4 ## is also prime.
Math100 said:
Proof:
Suppose ## p ## and ## p^{2}+8 ## are both prime numbers.
Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##.
Let ## p>3 ##.
Then ## p^{2}\equiv 1 \mod 3 ##,
so ## p^{2}+8\equiv 0 \mod 3 ##.
Note that ## p^{2}+8 ## can only be prime for ## p=3 ##.
Why is this true? It's not enough just to assert it.
Math100 said:
Thus ## p^{3}+4=27+4=31 ##, which is also prime.
Therefore, if ## p ## and ## p^{2}+8 ## are both prime numbers,
then ## p^{3}+4 ## is also prime.

Homework Statement:: If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that ## p^{3}+4 ## is also prime.
Relevant Equations:: None.

Proof:

Suppose ## p ## and ## p^{2}+8 ## are both prime numbers.
Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##.
Let ## p>3 ##.
Then ## p^{2}\equiv 1 \mod 3 ##,
How? You only have that ##p## is odd, i.e. ##p=2k+1## so ##p^2=4k^2+4k+1\equiv k(k+1)+1 \mod 3.## However, you used ##p^2\equiv 1 \mod 3## which is equivalent to ##k(k+1)\equiv 0 \mod 3.## Thus you have to prove: If ##p=2k+1>3## is prime, then either ##k## or ##k+1## is divisible by three. or the other way around: If ##k## and ##k+1## are not divisible by ##3## then ##2k+1## is composite. It is true, but you have to show why.
so ## p^{2}+8\equiv 0 \mod 3 ##.
Note that ## p^{2}+8 ## can only be prime for ## p=3 ##.
Thus ## p^{3}+4=27+4=31 ##, which is also prime.
Therefore, if ## p ## and ## p^{2}+8 ## are both prime numbers,
then ## p^{3}+4 ## is also prime.
What if ##p=3##?

This is another strange question. The condition that ##p^2 + 8## is prime only holds for ##p = 3##. That ##3^3 + 4 = 31## is prime seems a fairly random conclusion from ##p = 3##.

Last edited:
How? You only have that ##p## is odd, i.e. ##p=2k+1## so ##p^2=4k^2+4k+1\equiv k(k+1)+1 \mod 3.## However, you used ##p^2\equiv 1 \mod 3## which is equivalent to ##k(k+1)\equiv 0 \mod 3.## Thus you have to prove: If ##p=2k+1>3## is prime, then either ##k## or ##k+1## is divisible by three. or the other way around: If ##k## and ##k+1## are not divisible by ##3## then ##2k+1## is composite. It is true, but you have to show why.

What if ##p=3##?
If ## p=3 ##, then ## p^2+8=9+8=17 ##. Thus ## p^3+4=27+4=31 ##. But how should I prove that if ## p=2k+1>3 ## is prime, then either ## k ## or ## k+1 ## is divisible by ## 3 ##? And should I mention/include that if ## p=2 ##, then ## p^2+8=4+8=12 ##. Thus ## p^3+4=8+4=12 ##? This means ## p ## cannot be even, which is why I claimed ## p\neq 2 ## in my previous proof. But you said that I only have that ## p ## is odd. Then I need to show ## p=2 ## doesn't necessarily work for ## p^2+8 ## and ## p^3+4 ##.

Homework Statement:: If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that ## p^{3}+4 ## is also prime.
Relevant Equations:: None.

Proof:

Suppose ## p ## and ## p^{2}+8 ## are both prime numbers.
Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##.
Let ## p>3 ##.
Then ## p^{2}\equiv 1 \mod 3 ##,
so ## p^{2}+8\equiv 0 \mod 3 ##.
Note that ## p^{2}+8 ## can only be prime for ## p=3 ##.
What you have proved at this point is that if ##p## is a prime number, then if ##p^2+8## is also prime, it must be that ##p=3## .
Thus ## p^{3}+4=27+4=31 ##, which is also prime.
Therefore, if ## p ## and ## p^{2}+8 ## are both prime numbers,
then ## p^{3}+4 ## is also prime.

If ## p=3 ##, then ## p^2+8=9+8=17 ##. Thus ## p^3+4=27+4=31 ##. But how should I prove that if ## p=2k+1>3 ## is prime, then either ## k ## or ## k+1 ## is divisible by ## 3 ##? And should I mention/include that if ## p=2 ##, then ## p^2+8=4+8=12 ##. Thus ## p^3+4=8+4=12 ##? This means ## p ## cannot be even, which is why I claimed ## p\neq 2 ## in my previous proof. But you said that I only have that ## p ## is odd. Then I need to show ## p=2 ## doesn't necessarily work for ## p^2+8 ## and ## p^3+4 ##.
I said you only have that ##p## is odd, because that is what you deduced from at that point. So ##p=2k+1## for some integer ##k##. If ##k## and ##k+1## are both coprime to ##3## then ##k\equiv 1 \mod 3## and ##k+1\equiv 2 \mod 3##. Therefore ##k=3m+1## for some integer ##m## and ##k\cdot(k+1) = \ldots ## and so on.

Remember that your goal is to show that ##p^2=(2k+1)^2 \equiv 1\mod 3.##

p is not multiple of 2 but OP made use of the fact that p is not multiple of 3 to deduce p^2 ##\equiv## 1 (mod 3), I think.

p is not multiple of 2 but OP made use of the fact that p is not multiple of 3 to deduce p^2 ##\equiv## 1 (mod 3), I think.
Maybe it helps the OP to analyze his proof in order to understand how to proofread those deductions.

Homework Statement:: If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that ## p^{3}+4 ## is also prime.
Condition ##(A)##: ##p## is prime
Condition ##(B)##: ##p^2+8## is prime
Conclusion ##(C)##: ##p^3+4## is prime

This is usually written as: ## (A) \wedge (B) \Longrightarrow (C)##.

An equivalent statement would be: ##\lnot (C) \Longrightarrow \lnot (A) \vee \lnot (B)##

which is in words: If ##(C)## is wrong then either ##(A)## is wrong or ##(B)## is wrong (or both). If ##p^3+8## is composite then either ##p## is composite, ##p^2+8## is composite or both are.

One of these statements has to be shown.

Relevant Equations:: None.

Proof:

Suppose ## p ## and ## p^{2}+8 ## are both prime numbers.
This is the direct version of the proof, i.e. ## (A) \wedge (B) \Longrightarrow (C)##.
Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##.
Since ## p^{2}+8 ## is prime and ##2^2+8=12## is not, it follows that ## p ## is odd, so ## p\neq 2 ##.

Let ## p>3 ##.
Why?

Better is: If ##p=3## then ##p^3+8=17## is prime and ##p^3+4=31## is also prime. Hence the statement is true for ##p=3## and we are allowed to assume ##p>3.##

Let ##p=2k+1## with ##k>1.## (We already know that ##p## is odd, and we assume ##p>3##.)

Then ## p^{2}\equiv 1 \mod 3 ##,
Why?

We have ##p^2=(2k+1)^2=4k^2+4k+1\equiv k^2+k+1 \mod 3.## In order to conclude ##p^2\equiv 1\mod 3## we have to show that ##k^2+k=k(k+1)\equiv 0 \mod 3.##

Otherwise, i.e. if ##k^2+k=k(k+1)\not\equiv 0 \mod 3## then ##3## doesn't divide ##k## nor ##k+1## which is only possible if ##k\equiv 1\mod 3 ## and ##k+1\equiv 2\mod 3.## Therefore there is an integer ##m## such that ##k=3m+1.## This means ##p=2k+1=6m+3## and ##3\,|\,p.## As ##p## is prime, we have ##p=3## which contradicts our assumption ##p>3.##

Therefore $$p^2\equiv 4k^2+k+1 \equiv k^2+k+1\equiv k(k+1)+1\equiv 0+1 \equiv 1\mod 3\,.$$

It is here, where the reader can see, why the assumption ##p>3## has been made in the first place.

so ## p^{2}+8\equiv 0 \mod 3 ##.

Note that ## p^{2}+8 ## can only be prime for ## p=3 ##.
Why?

Please give us a reason. Hint: Use the fact that ##p=2k+1## and ##k^2+k\equiv 0\mod 3## as seen in the consideration above.

The rest is obsolete. We already dealt with ##p=3## and assumed ##p>3.##

_________

What did we actually prove?

We have shown that if ##p## and ##p^2+8## are both prime, then ##p=3## since otherwise we get a contradiction. So if we set

Conclusion ##(D)##: ##p=3##

then we have shown ##(A)\wedge (B) \Longrightarrow (D).##
Now clearly ##(D) \Longrightarrow (C)## since ##3^3+4=31## is prime, which proves the initial statement.

However, conclusion ##(C)## is a corollary, a present, a gift. We get it on top without any extra work since we have proven the stronger statement ##(A)\wedge (B) \Longrightarrow (D).##

These are the elaborations and considerations you must do in order to prove something. A proof is meant to convince people. In order to convince somebody, including yourself, you have to find a chain of conclusions starting with ##(A)## and ##(B)## until you end up at ##(D).## I wrote ##(D)## because this is what we get. It is much stronger than ##(C)## and we always minimize assumptions and maximize conclusions in mathematics. So ##(C)## is indeed a corollary, not the major statement.

We have actually shown ##p^2\equiv 1\mod 3## for prime numbers ##p>3.## Everything else is a variation of this basic statement. And its shortest proof would have been
$$p^2-1=(p-1)(p+1)$$
If ##p>3## is prime, then ##(p-1\, , \,p\, , \,p+1)## contains a number divisible by ##3## which is not ##p.##

This is left if you strip all decorations and deviations.

I gave away this long text to demonstrate what you should try to achieve with your proofs. It is almost a complete solution, so it is what you should have done.

Last edited:
• Delta2 and PeroK
But why does "Since ## p^2+8 ## is prime and ## p^2+8>8>2 ##"? Where does ## p^2+8>8>2 ## come from? Also, how does ## p^2=(2k+1)^2=4k^2+4k+1\equiv k^2+k+1 \mod 3 ##? Where does ## 4k^2+4k+1\equiv k^2+k+1 \mod 3 ## come from?

But why does "Since ## p^2+8 ## is prime and ## p^2+8>8>2 ##"? Where does ## p^2+8>8>2 ## come from?
The conditions from post #1 are that both p and ##p^2 + 8## are prime. These two conditions are sufficient to eliminate the possibility that p = 2. I don't see the need for saying ##p^2 + 8 > 8## in order to conclude that ##p \ne 2##.

There is also a typo in the work shown by @fresh_42 in this line:
fresh_42 said:
Better is: If ##p=3## then ##p^3+8=17## is prime and ##p^3+4=31## is also prime. Hence the statement is true for ##p=3## and we are allowed to assume ##p>3.##
The equation ##p^3+8=17## should read ##p^2+8=17##.

Also, how does ## p^2=(2k+1)^2=4k^2+4k+1\equiv k^2+k+1 \mod 3 ##? Where does ## 4k^2+4k+1\equiv k^2+k+1 \mod 3 ## come from?
This is an application of the rules of modular arithmetic, specifically the second property amongst those listed after reflexivity, symmetry, and transitivity. See https://en.wikipedia.org/wiki/Modular_arithmetic.

• Math100 and Delta2
I just realized that ## p^2\not\equiv 1 \mod 3 ## for ## p>3 ##. So if ## p=2k+1 ## for ## k>1 ##, then ## p^2+8=(2k+1)^2+8=4k^2+4k+9\equiv k^2+k+3 \mod 3 ##.

I just realized that ## p^2\not\equiv 1 \mod 3 ## for ## p>3 ##.
Was this a typo? If p = 5, ##p^2 = 25 \equiv 1 \mod 3##. There are many more counterexamples.
So if ## p=2k+1 ## for ## k>1 ##, then ## p^2+8=(2k+1)^2+8=4k^2+4k+9\equiv k^2+k+3 \mod 3 ##.

I just realized that ## p^2\not\equiv 1 \mod 3 ## for ## p>3 ##. So if ## p=2k+1 ## for ## k>1 ##, then ## p^2+8=(2k+1)^2+8=4k^2+4k+9\equiv k^2+k+3 \mod 3 ##.
Do you read what I write?
We have actually shown ##p^2\equiv 1\mod 3## for prime numbers ##p>3.## Everything else is a variation of this basic statement. And its shortest proof would have been
$$p^2-1=(p-1)(p+1)$$
If ##p>3## is prime, then ##(p-1\, , \,p\, , \,p+1)## contains a number divisible by ##3## which is not ##p.##

• Math100
Suppose ## p ## and ## p^2+8 ## are both prime numbers.
Since ## p^2+8 ## is prime and ## 2^2+8=12 ## is not,
it follows that ## p ## is odd, so ## p\neq 2 ##.
Assume ## p=3 ##.
Then ## p^2+8=17 ## is prime and ## p^{3}+4=31 ## is also prime.
Thus, the statement is true for ## p=3 ##.
Let ## p>3 ## be an odd prime.
Then ## p\equiv 1 \mod 3 ## or ## p\equiv 2 \mod 3 ##.
Now we consider two cases.
Case #1: Suppose ## p\equiv 1 \mod 3 ##.
Then ## p^2+8\equiv 0 \mod 3 ##.
Thus ## p^2+8 ## is not prime.
Case #2: Suppose ## p\equiv 2 \mod 3 ##.
Then ## p^2+8\equiv 0 \mod 3 ##.
Thus ## p^2+8 ## is not prime.
This means ## p^2+8 ## can only be prime for ## p=3 ##,
so ## p^{3}+4=3^{3}+4=31 ## is also prime.
Therefore, if ## p ## and ## p^2+8 ## are both prime numbers,
then ## p^{3}+4 ## is also prime.

• anuttarasammyak
How? You only have that ##p## is odd
p is not 2 because 12 is not prime. Once that is shown the parity of p is irrelevant.

He knows that p is prime, which is much more important.

What if ##p=3##?
He assumed p > 3. For that reason p is not equal to 3.

I
Suppose ## p ## and ## p^2+8 ## are both prime numbers.
Since ## p^2+8 ## is prime and ## 2^2+8=12 ## is not,
it follows that ## p ## is odd, so ## p\neq 2 ##.
The conclusion that "## p ## is odd" is illogical and irrelevant. It follows immediately that p is not 2. From that you can conclude that p is odd, but it is still irrelevant.
Assume ## p=3 ##.
Then ## p^2+8=17 ## is prime and ## p^{3}+4=31 ## is also prime.
Thus, the statement is true for ## p=3 ##.
Let ## p>3 ## be an odd prime.
oddness is still irrelevant
Then ## p\equiv 1 \mod 3 ## or ## p\equiv 2 \mod 3 ##.
Now we consider two cases.
You don't need cases. Just calculate ## 1^2 \bmod 3 ## and ## 2^2 \bmod 3 ##. They have the same value. What is it? Add 8 and mod by 3. What do you get?

By the way, you should use \bmod for the binary operator so you don't get excess space in front of it. Only use \mod for the congruence relation, i.e., with parentheses.