1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 22, 2015 #1

    s3a

    User Avatar

    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!
     
  2. jcsd
  3. Apr 22, 2015 #2
    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.
     
  4. Apr 22, 2015 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  5. Apr 22, 2015 #4
    This is a really easy problem, read a little bit of congruence theory.......
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted