Prove that if p is a prime number larger than 3, then p^2 = 6k + 1 for some k ∈ ℤ.
"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."
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!