Results 1 to 5 of 5

Math Help - Solving congruences using primitive roots

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    289

    Solving congruences using primitive roots

    Given that 3 is a primitive root modulo 17, determine all solutions to the congruence x^5 \equiv 6 \pmod{17}

    Since 3 is a primitive root we have: x = 3^m and so

    (3^m)^5 \equiv 6 \pmod{17}

    I am not sure how to progress on from here...

    cheers for any help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by usagi_killer View Post
    Given that 3 is a primitive root modulo 17, determine all solutions to the congruence x^5 \equiv 6 \pmod{17}

    Since 3 is a primitive root we have: x = 3^m and so

    (3^m)^5 \equiv 6 \pmod{17}

    I am not sure how to progress on from here...

    cheers for any help!


    We work modulo 17 in the following:

    3^{5m}=6=2\cdot 3\Longrightarrow 3^{5m-1}=2=3^{14}\Longrightarrow 5m-1=14\Longrightarrow...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    ohh thanks very much, i actually just figured out another method, is this correct?

    3^{5m} \equiv 6 \equiv 3^{15} \pmod{17}

    \implies 5m \equiv 15 \pmod{16}

    \implies -3 \times 5m \equiv 15 \times -3 \pmod{16}

    \implies m \equiv -45 \equiv 3 \pmod{16}

    Thus x = 3^3 \equiv 10 \pmod{17}

    So the solution is x \equiv 10 \pmod{17}

    Is this valid?

    Cheers!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by usagi_killer View Post
    Given that 3 is a primitive root modulo 17, determine all solutions to the congruence x^5 \equiv 6 \pmod{17}

    Since 3 is a primitive root we have: x = 3^m and so

    (3^m)^5 \equiv 6 \pmod{17}

    I am not sure how to progress on from here...

    cheers for any help!
    Multiplying the congruence x^5\equiv6\pmod{17} by 3 we get, equivalently, 3x^5\equiv18\equiv1\pmod{17}.

    There exists a positive integer m such that x\equiv3^m\pmod{17} and so 3x^5\equiv3^{5m+1}\equiv{17}. Finally, 3^{5m+1}\equiv1\equiv3^{16}\pmod{17}, which is equivalent to solving 5m+1\equiv{16}\equiv0\pmod{16}. The solution in the range 0\leq i\leq16 is m=3.

    The solutions of the original congruence are given by x\equiv3^3\equiv10\pmod{17}.
    Last edited by melese; March 23rd 2011 at 07:12 AM. Reason: It should be 3^3 - usagi_killer corrected me.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Quote Originally Posted by melese View Post
    Multiplying the congruence x^5\equiv6\pmod{17} by 3 we get, equivalently, 3x^5\equiv18\equiv1\pmod{17}.

    There exists a positive integer m such that x\equiv3^m\pmod{17} and so 3x^5\equiv3^{5m+1}\equiv{17}. Finally, 3^{5m+1}\equiv1\equiv3^{16}\pmod{17}, which is equivalent to solving 5m+1\equiv{16}\equiv0\pmod{16}. The solution in the range 0\leq i\leq16 is m=3.

    The solutions of the original congruence are given by x\equiv3^5\equiv10\pmod{17}.
    Thanks heaps for the help!

    But for the last congruence you mean x \equiv 3^3 \equiv 10 \pmod{17} right? :P
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive roots
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 9th 2011, 10:13 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 11th 2009, 05:03 AM
  3. Primitive roots mod p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 11th 2009, 02:03 PM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 08:09 PM
  5. i need help in primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 13th 2007, 04:51 PM

Search Tags


/mathhelpforum @mathhelpforum