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

[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!

 

[tnich]

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?

 

[s3a]

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:
But, why ask me that specifically about the number 6?

 

[tnich]

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

Edit:
But, why ask me that specifically about the number 6?

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

 

[s3a]

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

 

[Ray Vickson]

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.

 

[tnich]

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?

 

[s3a]

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?

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

Is that what you're asking?

 

[SammyS]

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

Is that what you're asking?

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

 

[s3a]

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?)

 

[SammyS]

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, p² = (2k + 1)² = 4k² +4k +1 . This can be shown to be 2m + 1 for some m, (which is related to k.)
Thus p² mod 2 = 1 for any prime p > 3 .

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

 

[s3a]

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.

 

[tnich]

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?

 

[SammyS]

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 p² = 6k + 1, i.e. p² 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.

 

[Ray Vickson]

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.

 

[WWGD]

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!

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

 

[Ray Vickson]

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