Prove that if p > 3 is prime, then p^2 = 6k + 1.

[s3a]

Homework Statement

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

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

Homework Equations

Modulo computations.

The Attempt at a Solution

I understand why the remainder/value of p mod 6 cannot be 0, 2 or 4, because the non-remainder part would be divisible by 6 (and therefore divisible by 2), and the remainder part would also be divisible by 2, therefore the entire number p would be divisible by 2, which would mean that it is even, and if a number greater than 3 is even then it is divisible by a number other than 1 or itself, so it is not prime.

I also get that p mod 6 = 3 would mean that p is a multiple of 3, and p cannot be 3 (since it must be larger than 3 as stated in the problem), but I don't get why it cannot be other multiples of 3 like 9.

And, I don't get why the solution is computing p mod 6 in the first place.

As for evaluating the p mod 6 = 1 and p mod 6 = 5 cases, I do understand what's going on there.

Could someone please help me fully understand what the solution is saying?

Any input would be GREATLY appreciated!

 

[metapuff]

Like you said, we know for sure that p = 1 (mod 6) or p = 5 (mod 6). If p = 1 (mod 6), then p^2 = 1^2 = 1 (mod 6), and we're done. Else, p = 5 = -1 (mod 6), and so p^2 = (-1)*(-1) = 1 (mod 6). p can't equal 3 mod 6, else it'd be divisible by 3 (like 9), and p wouldn't be prime.

 

[PeroK]

I also get that p mod 6 = 3 would mean that p is a multiple of 3, and p cannot be 3 (since it must be larger than 3 as stated in the problem), but I don't get why it cannot be other multiples of 3 like 9.

And, I don't get why the solution is computing p mod 6 in the first place.

On the first point, why not construct a short proof yourself to show that:

If p = 3 mod 6 then p is divisible by 3. Hence p is not prime (p > 3).

On the second point, the proof is in two parts. First, it establishes which congruences mod 6 are potentially prime: only 1 and 5. Then shows that both, when squared, are equal to 1 mod 6.

You could try an alternative proof starting with $p^2 mod 6$ and working back. But it wouldn't be as neat.

 

[certainly]

This is a really easy problem, read a little bit of congruence theory...