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

  • Thread starter s3a
  • Start date
  • #1
s3a
805
8

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!
 

Answers and Replies

  • #2
tnich
Homework Helper
1,048
336

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?
 
  • #3
s3a
805
8
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?
 
  • #4
tnich
Homework Helper
1,048
336
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?
 
  • #5
s3a
805
8
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. :(
 
  • #6
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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.
 
  • #7
tnich
Homework Helper
1,048
336
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?
 
  • #8
s3a
805
8
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?
 
  • #9
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,358
1,031
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 ( p2 mod 2 ) and ( p2 mod 3 ) for the above forms.?
 
  • #10
s3a
805
8
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?)
 
  • #11
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,358
1,031
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 .
 
  • #12
s3a
805
8
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.
 
  • #13
tnich
Homework Helper
1,048
336
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?
 
  • #14
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,358
1,031
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:
  • #15
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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.
 
  • #16
WWGD
Science Advisor
Gold Member
5,421
3,685

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 ##?
 
  • #17
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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).
 

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

Replies
3
Views
2K
Replies
14
Views
2K
Replies
9
Views
5K
  • Last Post
Replies
3
Views
5K
Replies
10
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
14
Views
7K
Top