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!

Homework Help: Proof: any prime number greater than 3 is congruent to 1 or 5 mod 6

  1. Oct 23, 2005 #1
    I'm trying to prove that any prime number bigger than 3 is congruent to 1 or 5 modulo 6. I started out by saying that that is the same as saying all prime numbers bigger than 3 are in the form 6n +- 1, n is an integer since 1 or 5 mod 6 yields either 1 or -1 and if you divide 6n+-1 by 6, you also get 1 or -1. But not i have no idea how to continue. any help will be appreciated. thank you
  2. jcsd
  3. Oct 23, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    I think you are basically assuming what you set out to prove.

    You may want to consider that if p > 3 is prime then both p-1 and p+1 are even (equivalent to 0 mod 2) and at least one of them equivalent to 1 or 2 mod 3. Does that lead anywhere?
  4. Oct 23, 2005 #3
    Tide, by first assuming what you said (p>3 is prime then both p-1 and p+1 are even),

    1. Assume p>3, p+-1 are even
    2. P+-1 = 2n , n is an integer
    3. p+-1 = 2n congruent to 0 mod 2
    4. p+-1 = 2(3n) = 6n congruent to 0 mod 6
    5. p = 6n +- 1
    6. p = 6n -1 congruent to 5 mod 6
    7. p = 6n +1 congruent to 1 mod 6

    is this the correct way to do it? it seems like im not really proving anything here because you first assumed that p>3 P+-1 is even, but didnt prove that it is in fact even. and the part where i went from 2n to 6n seems incorrect. help please.
  5. Oct 23, 2005 #4
    Perhaps you could try looking at it the following way. I don't know if it is much help though.

    [tex]a \equiv b\left( {\bmod 6} \right),b \in \left\{ {\mathop 0\limits^\_ ,\mathop 1\limits^\_ ,\mathop 2\limits^\_ ,\mathop 3\limits^\_ ,\mathop 4\limits^\_ ,\mathop 5\limits^\_ } \right\},a \in Z[/tex]

    You could then using the definition of a congruent to b modulo 6 and see if you can make some conclusions from that.

    Edit: You only need to show that if an integer is a prime and it is greater than 3 then it is congruent to 1 or 5 mod 6. So I think it is sufficient to simply knock out the numbers which do not satisfy the divisibility criteria.
    Last edited: Oct 23, 2005
  6. Oct 23, 2005 #5
    Any given integer is congruent to 0, or 1, ..., or 5 modulo 6

    Which integers can't be prime?
  7. Oct 23, 2005 #6
    Using this formula:
    [tex]a \equiv b\left( {\bmod 6} \right),b \in \left\{ {\mathop 0\limits^\_ ,\mathop 1\limits^\_ ,\mathop 2\limits^\_ ,\mathop 3\limits^\_ ,\mathop 4\limits^\_ ,\mathop 5\limits^\_ } \right\},a \in Z[/tex]
    which states that all whole numbers can be represented as either, 6n, 6n+1, 6n+2, 6n+3, 6n+4, or 6n+5, since 6n is a multiple of 6, 6n+2 and 6n+4 are multiples of 2, 6n+3 is a multiple of 3, this leaves 6n+1 and 6n+5 to be prime numbers. is this proof by exhausion or is it even a proof? can someone also tell me the name of the above formula?
    Last edited: Oct 23, 2005
  8. Oct 23, 2005 #7


    User Avatar
    Science Advisor
    Homework Helper


    Every prime number (except 2) is odd, otherwise it would be divisible by 2 and would not be prime! Therefore, p-1 and p+1 are both even.

    Now, since p itself is odd and NOT divisible by 3, it must be equivalent to either 1 or 2 mod 3. We already know that p = 1 mod 2.

    Here's one way to proceed (I'll let you fill in the gaps!)

    From the above deductions, either (a) [itex]p = 2m+1[/itex] and [itex]p = 3n+1[/itex] or (b) [itex]p = 2m+1[/itex] and [itex]p = 3n+2[/itex] where m and n are integers.

    In case (a), we have [itex]2m+1 = 3n+1[/itex] from which [itex]2m=3n[/itex]. Therefore, m is a multiple of 3 and n is even! You must conclude that p is a mulitple of 6 PLUS 1!

    Can you handle case (b)?
  9. Oct 23, 2005 #8
    Righty-oh, jhson114!
    You don't need to prove that some prime numbers are of 6n+1 and some of 6n+5 kind.
    You've just proven that all prime numbers can be 6n+1 or 6n+5 ONLY.
    Last edited: Oct 23, 2005
  10. Oct 23, 2005 #9
    for b, 2m +1 = 3n +2 => 2m = 3n+1. does this mean n is even and m is a multiple of 6 PLUS 1; therefore P must be... i dont know.. T.T I know what you did with a, but having that extra 1 totally confused me on how to go about after setting the two equations equal to each other.
  11. Oct 23, 2005 #10


    User Avatar
    Science Advisor

    That is a completely valid proof.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Proof prime number Date
Proof about 2 numbers being relatively prime. May 28, 2013
Number theory; primes dividing proof Sep 29, 2012
Abstract algebra proof involving prime numbers Sep 10, 2010
Another Prime number Proof Jan 23, 2010
Prime Number Proof Jan 23, 2010