Question

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

Answer 1

***Correct Solution***:
"Note that if p is a prime number larger than 3, then p mod 6 cannot be 0, 2, or 4 as this would mean p is even, and cannot be 3 as this would mean p is a multiple of 3.

The only two remaining cases are p mod 6 = 1 or p mod 6 = 5.

p mod 6 = 1:
Then p = 6k + 1 for some k ∈ Z. This means p 2 = 36k^2 + 12k + 1 = 6(6k^2 + 2k) + 1 = 6i + 1 where i = 6k^2 + 2k.

p mod 6 = 5:
Then p = 6k + 5 for some k ∈ Z. This means p 2 = 36k^2 + 60k + 25 = 6(6k^2 + 10k + 4) + 1 = 6i + 1 where i = 6k^2 + 10k + 4. In both cases, we have the desired result."

Answer 2

Several people tried to explain this to me, and I still don't get it. :(


Basically:

1) Why was m = 6 chosen in p mod m?

2) I get that p cannot be even, since if it were, it would not be prime. In other words, I understand why the cases p mod 6 = 0, p mod 6 = 2 and p mod 6 = 4 were rejected.

3) I don't get why the case p mod 6 = 3 is rejected.

4) I also don't get why the cases p mod 6 = 1 and p mod 6 = 5 ensure that p is prime.


If someone could make me finally understand this problem, I would REALLY appreciate it!