Results 1 to 11 of 11

Math Help - x^6 congruent to 1 (mod 19)

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    x^6 congruent to 1 (mod 19)

    How do solve x^6 \equiv 1 \textrm{ (mod 19)}

    NO SOLUTIONS PLEASE, just hints or even just which theorem/method to use.

    I thought it might be something to do with primitive roots...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello !
    Note that x^6 \equiv 1 \pmod{19} is equivalent to x^6 - 1 \equiv 0 \pmod{19}. Doesn't this remind you of some algebra´c structure learnt while studying factorization ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Deadstar View Post
    How do solve x^6 \equiv 1 \textrm{ (mod 19)}

    NO SOLUTIONS PLEASE, just hints or even just which theorem/method to use.

    I thought it might be something to do with primitive roots...

    The hint Bacterius gave you wraps it all, but if you insist in using primitive roots then suppose \omega is such a primitive root , and look at \omega^3 ...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Thanks for the hint but I probably should have asked about equations of the form x^n \equiv 1 mod p with p prime as the above hint for this one hasn't helped me.

    Factorizing that I can only see two solutions, 1 and 18.

    I can't find anything in our notes about this and it's stuck in the middle of a tutorial consisting of primitive root questions so I don't know how to approach it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tonio View Post
    The hint Bacterius gave you wraps it all, but if you insist in using primitive roots then suppose \omega is such a primitive root , and look at \omega^3 ...

    Tonio
    Isn't just required that  \omega is a cubic residue?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Deadstar View Post
    Thanks for the hint but I probably should have asked about equations of the form x^n \equiv 1 mod p with p prime as the above hint for this one hasn't helped me.

    Factorizing that I can only see two solutions, 1 and 18.


    How come?? x^6-1=(x-1)(x^2+x+1)(x+1)(x^2-x+1) <br />
. The roots 1,18=-1\!\!\!\pmod {19} are immediate, and we're left now with the quadratics, so let's check the discriminant which, by the way, is identical in both!:

    \Delta=1-4=-3 , and the questions of questions now is whether -3 is a quadratic residue modulo 19...but this is trivial and we don't even need quadatic reciprocity, right?

    The complete set of roots is -1,1,7,12,8,11

    Tonio


    I can't find anything in our notes about this and it's stuck in the middle of a tutorial consisting of primitive root questions so I don't know how to approach it.
    .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chiph588@ View Post
    Isn't just required that  \omega is a cubic residue?

    "Just"? I think that's exactly equivalent to ask whether the original equaion has a solution. There are \phi(18)=6 primitive roots of 19, which are (modulo 19, of course), if I'm not wrong (and I wouldn't bet much that I am not) 2,3,10,13,14,15 .

    Tonio
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    EDIT. Solving is happening...
    Last edited by Deadstar; March 2nd 2010 at 01:49 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Ok I can get 7 and 11 from the quadratics but since they both give the same result how do I find 8 and 12?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    I think you already worked out what I'm about to say, but this is just to increase my post count (joking )

    x^6 - 1 = (x - 1)(x + 1)(x^2 - x + 1)(x^2 + x + 1)

    So the solutions of x^6 \equiv 1 \pmod{19} are given by :

    x - 1 \equiv 0 \pmod{19}

    x + 1 \equiv 0 \pmod{19}

    x^2 - x + 1 \equiv 0 \pmod{19}

    x^2 + x + 1 \equiv 0 \pmod{19}

    Solve those for x and you will find all the solutions of the congruence. Don't forget to include the four solutions given by the quadratics
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Deadstar View Post
    Ok I can get 7 and 11 from the quadratics but since they both give the same result how do I find 8 and 12?

    What "same result" are you talking about? That they have the same discriminant doesn't mean their roots are the same....
    Just apply the well-known formula for the roots of a quadratic equation, which you can do since the characteristic of the field we're working on isn't two.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is S_3 congruent to D_3?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2011, 08:24 PM
  2. Congruent Triangles
    Posted in the Geometry Forum
    Replies: 6
    Last Post: December 29th 2008, 10:21 PM
  3. Congruent Angles
    Posted in the Geometry Forum
    Replies: 2
    Last Post: December 22nd 2008, 10:09 PM
  4. Congruent Segments
    Posted in the Geometry Forum
    Replies: 2
    Last Post: December 12th 2008, 05:32 PM
  5. congruent mod 9
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 11th 2007, 08:07 PM

Search Tags


/mathhelpforum @mathhelpforum