Results 1 to 5 of 5

Thread: Solving congruences using primitive roots

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    310

    Solving congruences using primitive roots

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

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

    $\displaystyle (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
    Thanks
    3
    Quote Originally Posted by usagi_killer View Post
    Given that 3 is a primitive root modulo 17, determine all solutions to the congruence $\displaystyle x^5 \equiv 6 \pmod{17}$

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

    $\displaystyle (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:

    $\displaystyle 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
    310
    ohh thanks very much, i actually just figured out another method, is this correct?

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

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

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

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

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

    So the solution is $\displaystyle 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 $\displaystyle x^5 \equiv 6 \pmod{17}$

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

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

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

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

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

    The solutions of the original congruence are given by $\displaystyle x\equiv3^3\equiv10\pmod{17}$.
    Last edited by melese; Mar 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
    310
    Quote Originally Posted by melese View Post
    Multiplying the congruence $\displaystyle x^5\equiv6\pmod{17}$ by $\displaystyle 3$ we get, equivalently, $\displaystyle 3x^5\equiv18\equiv1\pmod{17}$.

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

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

    But for the last congruence you mean $\displaystyle 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: Mar 9th 2011, 10:13 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 11th 2009, 05:03 AM
  3. Primitive roots mod p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 11th 2009, 02:03 PM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 17th 2008, 08:09 PM
  5. i need help in primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 13th 2007, 04:51 PM

Search Tags


/mathhelpforum @mathhelpforum