Results 1 to 8 of 8

Math Help - Every prime > 3 is congruent to \pm 1 mod 6

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Every prime > 3 is congruent to \pm 1 mod 6

    Every prime > 3 is congruent to \pm 1 \ \mbox{mod 6}

    Induction maybe?

    5\equiv\pm 1\ \mbox{(mod 6)} This isn't true though
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    any number can be

    0,1,2,3,4,5 mod 6

    because the number is prime - 0,2,3,4 can be ruled out
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    5\equiv -1\ \mbox{(mod 6)}, since 5-(-1)=6\times 1.

    You could try arguing along these lines: all primes greater than 3 are odd. Therefore, they must be congruent to either -1, 1, or 3 mod 6. (5 and -1 are equivalent). However, any number greater than 3 that is congruent to 3 mod 6 would be divisible by 3, and hence not prime. Therefore, all primes greater than 3 are congruent to 1 or -1 mod 6.

    [EDIT]: This is essentially the same as what aman_cc said.
    Last edited by Ackbeet; July 8th 2010 at 04:43 AM. Reason: Duplication.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by dwsmith View Post
    Every prime > 3 is congruent to \pm 1 \ \mbox{mod 6}

    Induction maybe?

    5\equiv\pm 1\ \mbox{(mod 6)} This isn't true though
    You can generalize and consider integers a that are relatively prime to 6 and the result will follow, in particular, to any prime p>3 .

    Let a=6q+r, with 0\leq r<6. Then gcd(a,6)=gcd(6,r), so we need only to look at values r such that gcd(6,r)=1. These are r=1,5.

    Now, a\equiv 1(mod\ 6),or a\equiv 5\equiv -1(mod\ 6).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Keep it simple ... I assume that p > 3 in the whole post by the way ... since the fact 3 | 3 does not contradict the primality of p ... just adjust what is below as you wish ...

    Let p \equiv x \pmod{n} \Rightarrow p = kn + x, k \in \mathbb{Z}, x \in \mathbb{Z}/n\mathbb{Z}
    Then it follows that \gcd{(n, x)} | p
    But if p is prime we must have \gcd{(n, x)} = 1 (otherwise there is a contradiction with respect to the definition of a prime number)

    Applying this to the current problem with n = 6, the only x that are coprime to 6 (in the congruence ring \mathbb{Z}/6\mathbb{Z} of course) are, surprisingly enough, 1 and 5 (which turns out to be congruent to -1 \pmod{6}).

    It follows that if p is indeed prime then it must be congruent to \pm 1 \pmod{6}

    ...

    Interestingly, it is also possible to prove that this implies that \gcd{(k, n)} = 1 for any prime p ... This gives me an idea, I'll be right back !
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    To Bacterius

    gcd(n,x) = 1 or p

    i.e. p = p mod p^2, so gcd(p^2,p) = p, and p|p

    But since n is 6, then we can say that gcd(n,x) should be 1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    I don't understand what you mean, can you develop ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    I was just pointing out that gcd(n,x) isn't necessarily 1, it could be p also, at least in general ... for this particular case, since n is 6, then gcd(n,x) would be 1 ...
    Last edited by Bingk; July 16th 2010 at 06:53 AM. Reason: added stuff :)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Is S_3 congruent to D_3?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2011, 07:24 PM
  3. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  4. x^6 congruent to 1 (mod 19)
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 2nd 2010, 06:54 PM
  5. Replies: 4
    Last Post: November 12th 2006, 05:00 PM

/mathhelpforum @mathhelpforum