1. The problem statement, all variables and given/known data 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." 2. Relevant equations Modulo computations. 3. 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!