- #1

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

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!