# Prove that if p > 3 is a prime number, then p^2 = [....]

• s3a
In summary, the goal of this problem is to prove that for any prime number larger than 3, p^2 can be written as 6k + 1 for some integer k. To do this, the concept of modulo is used to determine whether a number is a multiple of any number other than 1 and itself/p. The value of 6 is chosen as the divisor because it allows for two cases (p mod 6 = 1 and p mod 6 = 5) where p divided by 6 yields a number that is not a multiple of any number other than 1 and itself/p. This is proven by showing that p mod 6 = 1 and p mod 6 = 5 cannot be
s3a

## Homework Statement

Prove that if p is a prime number larger than 3, then ##p^2## = 6k + 1 for some k ∈ ℤ.

## Homework Equations

* Modulo
* Factoring
* Distribution or ##(ax + b)^2 = a^2 x^2 + 2abx + b^2## formula

## The Attempt at a Solution

The reason why p mod d = r_i, where r_i is the remainder value, which can range from 0 to 5 for the problem that is the focus of this post, or in general from 0 to d - 1, in general, where d is the divisor) is even done in the first place is because one determines whether a number is prime or not by whether it is a multiple of any number other than 1 and itself/p, and modulo stuff allows one to determine whether an integer variable divided by a certain fixed integer is a multiple of some integer. It is desired to find the case(s) (which are, later on in the solution's logic, found to be p mod 6 = 1 and p mod 6 = 5 in the problem that is the focus of this post) for which the integer variable (p) being divided by the fixed constant (d = 6) yields a number that is not a multiple of any number other than 1 and itself/p.

But, my main or only question for this entire post is, why is p being modded by the number 6, specifically? I suspect that it has something to do with the 6 in p^2 = 6k + 1, but if that's why the number 6 was chosen as the value of d, then I don't understand why that is. Could someone please clarify this for me?

Other stuff that I believe I understand (just for background information):
The p (not squared) = 6k + 1 part simply follows from the p mod 6 = 1 part.

The p (not squared) = 6k + 5 part simply follows from the p mod 6 = 5 part.

---

p mod 6 = 0 ⇒ p = 6k + 0 ⇒ p = 6k ⇒ p = 2(3k) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 2 ⇒ p = 6k + 2 ⇒ p = 2(3k + 1) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 4 ⇒ p = 6k + 4 ⇒ p = 2(3k + 2) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

---

p mod 6 = 3 ⇒ p = 6k + 3 ⇒ 3(2k + 1) ⇒ p is a multiple of 3 (p being a multiple of 3 is a bad thing because being a multiple of any number other than 1 or p means that p is not a prime number, but it is supposed to be, by definition - if p = 3, which it cannot be, by definition, then that would not be a bad thing because the number p = 3 would only be a multiple of 1 and p = 3)

---

One knows that p mod 6 = 1 is a valid case because p mod 6 = 1 ⇒ p = 6k + 1, and 6k + 1 cannot be factored, and the fact that 6k + 1 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 1.

Similarly, one knows that p mod 6 = 5 is a valid case because p mod 6 = 5 ⇒ p = 6k + 5, and 6k + 5 cannot be factored, and the fact that 6k + 5 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 5.

---

Any input would be GREATLY appreciated!

s3a said:

## Homework Statement

Prove that if p is a prime number larger than 3, then ##p^2## = 6k + 1 for some k ∈ ℤ.

## Homework Equations

* Modulo
* Factoring
* Distribution or ##(ax + b)^2 = a^2 x^2 + 2abx + b^2## formula

## The Attempt at a Solution

The reason why p mod d = r_i, where r_i is the remainder value, which can range from 0 to 5 for the problem that is the focus of this post, or in general from 0 to d - 1, in general, where d is the divisor) is even done in the first place is because one determines whether a number is prime or not by whether it is a multiple of any number other than 1 and itself/p, and modulo stuff allows one to determine whether an integer variable divided by a certain fixed integer is a multiple of some integer. It is desired to find the case(s) (which are, later on in the solution's logic, found to be p mod 6 = 1 and p mod 6 = 5 in the problem that is the focus of this post) for which the integer variable (p) being divided by the fixed constant (d = 6) yields a number that is not a multiple of any number other than 1 and itself/p.

But, my main or only question for this entire post is, why is p being modded by the number 6, specifically? I suspect that it has something to do with the 6 in p^2 = 6k + 1, but if that's why the number 6 was chosen as the value of d, then I don't understand why that is. Could someone please clarify this for me?

Other stuff that I believe I understand (just for background information):
The p (not squared) = 6k + 1 part simply follows from the p mod 6 = 1 part.

The p (not squared) = 6k + 5 part simply follows from the p mod 6 = 5 part.

---

p mod 6 = 0 ⇒ p = 6k + 0 ⇒ p = 6k ⇒ p = 2(3k) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 2 ⇒ p = 6k + 2 ⇒ p = 2(3k + 1) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 4 ⇒ p = 6k + 4 ⇒ p = 2(3k + 2) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

---

p mod 6 = 3 ⇒ p = 6k + 3 ⇒ 3(2k + 1) ⇒ p is a multiple of 3 (p being a multiple of 3 is a bad thing because being a multiple of any number other than 1 or p means that p is not a prime number, but it is supposed to be, by definition - if p = 3, which it cannot be, by definition, then that would not be a bad thing because the number p = 3 would only be a multiple of 1 and p = 3)

---

One knows that p mod 6 = 1 is a valid case because p mod 6 = 1 ⇒ p = 6k + 1, and 6k + 1 cannot be factored, and the fact that 6k + 1 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 1.

Similarly, one knows that p mod 6 = 5 is a valid case because p mod 6 = 5 ⇒ p = 6k + 5, and 6k + 5 cannot be factored, and the fact that 6k + 5 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 5.

---

Any input would be GREATLY appreciated!
What relationship does prime ##p## have to the prime factors of 6?

tnich said:
What relationship does prime ##p## have to the prime factors of 6?
It is divisible by them (since all numbers can be written as a product of only prime numbers)?

Edit:

s3a said:
It is divisible by them (since all numbers can be written as a product of only prime numbers)?

Edit:
What are the prime factors of 6? How is p related to each of them?

tnich said:
What are the prime factors of 6? How is p related to each of them?
The prime factors of 6 are 2 and 3. The variable p is not divisible by either one of them (so, I believe I made a mistake in my previous reply to you) since p is only divisible by 1 and itself, and it is a number greater than 3 (so it's neither 2 nor 3 - both of which are prime).

I still don't get why the number 6 matters, though. Sorry if I'm still not getting what you're likely trying to make me see for myself. :(

s3a said:
The prime factors of 6 are 2 and 3. The variable p is not divisible by either one of them (so, I believe I made a mistake in my previous reply to you) since p is only divisible by 1 and itself, and it is a number greater than 3 (so it's neither 2 nor 3 - both of which are prime).

I still don't get why the number 6 matters, though. Sorry if I'm still not getting what you're likely trying to make me see for myself. :(

The number 6 matters because the question was specifically about something being divisible by 6.

Anyway, ##p^2 - 1 = (p-1)(p+1)##, and since any prime number ##p > 2## is odd, both ##p-1## and ##p+1## are divisible by two. It is easy to see directly that for ##p = 5, 7, 11, 13, \ldots## (up to some quite large limit) that ##p## prime implies that one of ##p-1## or ##p+1## is divisible by 3. However, I do not yet have a proof.

s3a said:
The prime factors of 6 are 2 and 3. The variable p is not divisible by either one of them (so, I believe I made a mistake in my previous reply to you) since p is only divisible by 1 and itself, and it is a number greater than 3 (so it's neither 2 nor 3 - both of which are prime).

I still don't get why the number 6 matters, though. Sorry if I'm still not getting what you're likely trying to make me see for myself. :(
What is ##p## mod 2? What is ##p## mod 3?

Ray Vickson said:
The number 6 matters because the question was specifically about something being divisible by 6.

Anyway, ##p^2−1 = (p−1)(p+1)##, and since any prime number ##p > 2## is odd, both ##p−1## and ##p+1## are divisible by two. It is easy to see directly that for p=5,7,11,13,… (up to some quite large limit) that p prime implies that one of p−1 or p+1 is divisible by 3. However, I do not yet have a proof.
But, it's the squared number minus 1 that's divisible by 6. How is one supposed to deduce that the non-squared/original number plus or minus some constant should be analyzed for when it is divisible by 6?

tnich said:
What is p mod 2? What is p mod 3?
I believe p mod 2 can be either 0 or 1 and p mod 3 can be either 0, 1 or 2.

But, since we know p is a prime number larger than 3, then p mod 2 = 1 (because p = 2k + 0 = 2(k) and p = 2k + 2 = 2(k+1), so both are divisible by a number other than 1 or p).

Similarly, p mod 3 = 1 or 2 (because p = 3k + 0 = 3(k), which is divisible bya number other than 1 or p).

s3a said:
I believe p mod 2 can be either 0 or 1 and p mod 3 can be either 0, 1 or 2.

But, since we know p is a prime number larger than 3, then p mod 2 = 1 (because p = 2k + 0 = 2(k) and p = 2k + 2 = 2(k+1), so both are divisible by a number other than 1 or p).

Similarly, p mod 3 = 1 or 2 (because p = 3k + 0 = 3(k), which is divisible bya number other than 1 or p).

So, what are ( p2 mod 2 ) and ( p2 mod 3 ) for the above forms.?

SammyS said:
So, what are ( p2 mod 2 ) and ( p2 mod 3 ) for the above forms.?
Oh! Is it the case that p^2 mod 2 = p mod 2 and p^2 mod 3 = p mod 3? So, if p plus or minus some constant is divisible by 6, then it follows that p^2 plus or minus some constant is also divisible by 6, and that is why the proof starts with p mod 6 (since it ensures that p^2 plus or minus some constant is divisible by 6), right?

(I'm not sure that I understand why d = 2 and d = 3, in the examples of tnich, though. Are the values d = 2 and d = 3 used just to keep the numbers small to use as easy test cases for a thought experiment?)

s3a said:
Oh! p^2 mod 2 = p mod 2 and p^2 mod 3 = p mod 3? So, if p plus or minus some constant is divisible by 6, then it follows that p^2 plus or minus some constant is also divisible by 6, and that is why the proof starts with p mod 6, right?

(I'm not sure that I understand why d = 2 and d = 3, in the examples of tnich, though. Are the values d = 2 and d = 3 used just to keep the numbers small to use as easy test cases for a thought experiment?)
That's not what I intended.

Example:
If (p mod 2) = 1 , that means p = 2k +1 for some integer k. Right ?
Therefore, p2 = (2k + 1)2 = 4k2 +4k +1 . This can be shown to be 2m + 1 for some m, (which is related to k.)
Thus p2 mod 2 = 1 for any prime p > 3 .

Do similar for the two possibilities you gave for p mod 3 .

Oh.

I understand the rest of the steps in the proof, but that's not what I'm confused about. What I am confused about is, in the very beginning of the proof, why wanting to analyze the divisibility of p^2 by 6 means that one wants to analyze the divisibility of p by 6 too.

To do what you asked for, though.:
p mod 3 = 1 --> p = 3k + 1 --> p^2 = 9k^2 + 6k + 1 --> p^2 = 3(3k^2+2k) + 1

p mod 3 = 2 --> p = 3k + 2 -->p^2 = 9k^2 + 12k + 4 --> p^2 = 3(3k^2 + 4k + 1) + 1

Edit:
What you wanted me to do shows me a pattern of p mod d yielding p^2 = d*c + 1, but that's not the confusion that this thread is about; the confusion this thread is about is what I bolded in this post.

s3a said:
What I am confused about is, in the very beginning of the proof, why wanting to analyze the divisibility of p^2 by 6 means that one wants to analyze the divisibility of p by 6 too.
You seem to be asking about details of a proof that we have not seen, yet. We have seen that ##p \equiv \pm 1 \mod 3 \implies p^2 \equiv 1 \mod 3##. What does ##p \equiv \pm 1 \mod 6## imply?

s3a said:
Oh.

I understand the rest of the steps in the proof, but that's not what I'm confused about. What I am confused about is, in the very beginning of the proof, why wanting to analyze the divisibility of p^2 by 6 means that one wants to analyze the divisibility of p by 6 too.
...
Oh !
That clarifies (for me) what is the major question you are raising in this thread.

In the OP of this thread, you show that if any prime number, p, is greater than 3, then (p mod 6) must be either 1 or 5, in other words there is some integer, n, such that either p = 6n + 1 or p = 6n + 5 .

Square each of these to finish the proof that p2 = 6k + 1, i.e. p2 mod 6 = 1 .
That will finish up the proof very nicely.

In the end, that may be easier than combining the mod 2 and mod 3 results to show that the mod 6 result is true.

Last edited:
s3a said:
Oh.

I understand the rest of the steps in the proof, but that's not what I'm confused about. What I am confused about is, in the very beginning of the proof, why wanting to analyze the divisibility of p^2 by 6 means that one wants to analyze the divisibility of p by 6 too.

To do what you asked for, though.:
p mod 3 = 1 --> p = 3k + 1 --> p^2 = 9k^2 + 6k + 1 --> p^2 = 3(3k^2+2k) + 1

p mod 3 = 2 --> p = 3k + 2 -->p^2 = 9k^2 + 12k + 4 --> p^2 = 3(3k^2 + 4k + 1) + 1

Edit:
What you wanted me to do shows me a pattern of p mod d yielding p^2 = d*c + 1, but that's not the confusion that this thread is about; the confusion this thread is about is what I bolded in this post.

No: ##p## is not divisible by 6, nor is ##p^2##. You need to be looking at ##p^2 - 1##, because that is not a prime number and so can be divisible by lots of things. Go back and re-read #6.

s3a said:

## Homework Statement

Prove that if p is a prime number larger than 3, then ##p^2## = 6k + 1 for some k ∈ ℤ.

## Homework Equations

* Modulo
* Factoring
* Distribution or ##(ax + b)^2 = a^2 x^2 + 2abx + b^2## formula

## The Attempt at a Solution

The reason why p mod d = r_i, where r_i is the remainder value, which can range from 0 to 5 for the problem that is the focus of this post, or in general from 0 to d - 1, in general, where d is the divisor) is even done in the first place is because one determines whether a number is prime or not by whether it is a multiple of any number other than 1 and itself/p, and modulo stuff allows one to determine whether an integer variable divided by a certain fixed integer is a multiple of some integer. It is desired to find the case(s) (which are, later on in the solution's logic, found to be p mod 6 = 1 and p mod 6 = 5 in the problem that is the focus of this post) for which the integer variable (p) being divided by the fixed constant (d = 6) yields a number that is not a multiple of any number other than 1 and itself/p.

But, my main or only question for this entire post is, why is p being modded by the number 6, specifically? I suspect that it has something to do with the 6 in p^2 = 6k + 1, but if that's why the number 6 was chosen as the value of d, then I don't understand why that is. Could someone please clarify this for me?

Other stuff that I believe I understand (just for background information):
The p (not squared) = 6k + 1 part simply follows from the p mod 6 = 1 part.

The p (not squared) = 6k + 5 part simply follows from the p mod 6 = 5 part.

---

p mod 6 = 0 ⇒ p = 6k + 0 ⇒ p = 6k ⇒ p = 2(3k) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 2 ⇒ p = 6k + 2 ⇒ p = 2(3k + 1) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 4 ⇒ p = 6k + 4 ⇒ p = 2(3k + 2) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

---

p mod 6 = 3 ⇒ p = 6k + 3 ⇒ 3(2k + 1) ⇒ p is a multiple of 3 (p being a multiple of 3 is a bad thing because being a multiple of any number other than 1 or p means that p is not a prime number, but it is supposed to be, by definition - if p = 3, which it cannot be, by definition, then that would not be a bad thing because the number p = 3 would only be a multiple of 1 and p = 3)

---

One knows that p mod 6 = 1 is a valid case because p mod 6 = 1 ⇒ p = 6k + 1, and 6k + 1 cannot be factored, and the fact that 6k + 1 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 1.

Similarly, one knows that p mod 6 = 5 is a valid case because p mod 6 = 5 ⇒ p = 6k + 5, and 6k + 5 cannot be factored, and the fact that 6k + 5 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 5.

---

Any input would be GREATLY appreciated!
s3a said:

## Homework Statement

Prove that if p is a prime number larger than 3, then ##p^2## = 6k + 1 for some k ∈ ℤ.

## Homework Equations

* Modulo
* Factoring
* Distribution or ##(ax + b)^2 = a^2 x^2 + 2abx + b^2## formula

## The Attempt at a Solution

The reason why p mod d = r_i, where r_i is the remainder value, which can range from 0 to 5 for the problem that is the focus of this post, or in general from 0 to d - 1, in general, where d is the divisor) is even done in the first place is because one determines whether a number is prime or not by whether it is a multiple of any number other than 1 and itself/p, and modulo stuff allows one to determine whether an integer variable divided by a certain fixed integer is a multiple of some integer. It is desired to find the case(s) (which are, later on in the solution's logic, found to be p mod 6 = 1 and p mod 6 = 5 in the problem that is the focus of this post) for which the integer variable (p) being divided by the fixed constant (d = 6) yields a number that is not a multiple of any number other than 1 and itself/p.

But, my main or only question for this entire post is, why is p being modded by the number 6, specifically? I suspect that it has something to do with the 6 in p^2 = 6k + 1, but if that's why the number 6 was chosen as the value of d, then I don't understand why that is. Could someone please clarify this for me?

Other stuff that I believe I understand (just for background information):
The p (not squared) = 6k + 1 part simply follows from the p mod 6 = 1 part.

The p (not squared) = 6k + 5 part simply follows from the p mod 6 = 5 part.

---

p mod 6 = 0 ⇒ p = 6k + 0 ⇒ p = 6k ⇒ p = 2(3k) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 2 ⇒ p = 6k + 2 ⇒ p = 2(3k + 1) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

p mod 6 = 4 ⇒ p = 6k + 4 ⇒ p = 2(3k + 2) ⇒ p is even (p cannot be even, since p is a prime number larger than 3 and a prime number larger than 3 cannot be even because being even means being a multiple of 2 and being a multiple of any number other than 1 or p means that p is not a prime number, but is is supposed to be, by definition)

---

p mod 6 = 3 ⇒ p = 6k + 3 ⇒ 3(2k + 1) ⇒ p is a multiple of 3 (p being a multiple of 3 is a bad thing because being a multiple of any number other than 1 or p means that p is not a prime number, but it is supposed to be, by definition - if p = 3, which it cannot be, by definition, then that would not be a bad thing because the number p = 3 would only be a multiple of 1 and p = 3)

---

One knows that p mod 6 = 1 is a valid case because p mod 6 = 1 ⇒ p = 6k + 1, and 6k + 1 cannot be factored, and the fact that 6k + 1 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 1.

Similarly, one knows that p mod 6 = 5 is a valid case because p mod 6 = 5 ⇒ p = 6k + 5, and 6k + 5 cannot be factored, and the fact that 6k + 5 cannot be factored means that p is not a multiple of anything other than 1 or p = 6k + 5.

---

Any input would be GREATLY appreciated!
I am not sure if this was covered in other posts, but 11 seems like an exception. Maybe you meant ##p=6k \pm 1 ##?

s3a said:
But, it's the squared number minus 1 that's divisible by 6. How is one supposed to deduce that the non-squared/original number plus or minus some constant should be analyzed for when it is divisible by 6?

Read #6 again. It looks at ##p^2-1## and factors that into ##(p-1)(p+1)##. Both ##p-1## and ##p+1## are even, so are each divisible by 2. Then I remarked that it looks like for any prime ##p \geq 5## that either ##p-1## is divisible by 3 or ##p+1## is divisible by 3 (true in hundreds of examples, but not yet proven). Since both are factors of ##p^2-1##, the latter must also be divisible by 3, and also is divisible by 2 (being an even number).

## What is the statement being proven?

The statement being proven is that if p is a prime number greater than 3, then p^2 is equal to a certain value.

## Why is p required to be a prime number greater than 3?

In order for the statement to be true, p must be a prime number greater than 3. This is because any number less than 3 can easily be proven to satisfy the statement (as 1^2 = 1 and 2^2 = 4). Therefore, by requiring p to be a prime number greater than 3, it ensures that the statement is not true for all numbers and must be proven.

## What is the proof for this statement?

The proof for this statement involves using the Fundamental Theorem of Arithmetic, which states that every positive integer can be expressed as a unique product of prime numbers. By using this theorem, we can show that p^2 can only be equal to a specific value if p is a prime number greater than 3.

## Can this statement be proven for all prime numbers?

No, this statement can only be proven for prime numbers greater than 3. This is because for prime numbers less than 3, the statement does not hold true. For example, if p = 2, then p^2 = 4, which is not equal to a specific value.

## What are the implications of this statement in the field of mathematics?

This statement is important in the field of mathematics as it helps to demonstrate the power and usefulness of the Fundamental Theorem of Arithmetic. It also shows how specific conditions must be met in order for a statement to be true, and how these conditions can be proven using mathematical reasoning and principles.

• Calculus and Beyond Homework Help
Replies
3
Views
852
• Calculus and Beyond Homework Help
Replies
30
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
3K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
30
Views
3K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
2K