- #1

- 807

- 8

## 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!