Results 1 to 5 of 5

Math Help - [SOLVED] Solutions of Congruences

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    119

    [SOLVED] Solutions of Congruences

    Problem: Find all the solutions of the following congruence:
     3x^5 \equiv 1 ( \mod{23} )

    Since 5 is a primitive root of 23. I constructed an index table modulo 23 for the p.r. 5.

    Number: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
    Index : 22, 2, 16, 4, 1, 18, 19, 6, 10, 3, 9, 20, 14, 21, 17, 8, 7, 12, 15, 5, 13, 11

    Now, since  3x^5 \equiv 1 ( \pmod{23} ) can be rewritten in indices as

     ind_{5}3+5ind_{5}x \equiv ind_{5}1 \pmod{22}

    By looking at the index table, we get

     16 + 5ind_{5}x \equiv 22  \pmod{22}

    Let y = 5ind_{5}x,

    we get

     16 + 5y \equiv 22  \pmod{22}

    Then, subtract 16 from both sides

     5y \equiv 6 \pmod{22}

    From here I am stuck. I believe I am supposed to multiply 5 by some number to get 1 mod 22. From here I can solve for y and then for x.

    Any help is greatly appreciated. Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    I would start by saying that 3\times8=24\equiv1\!\!\!\pmod{23}. Then if you multiply both sides of the congruence 3x^5\equiv1\!\!\!\pmod{23} by 8, it becomes x^5\equiv8\!\!\!\pmod{23}, and you can read off the answer for x directly from the index table.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2008
    Posts
    119
    Opalg, I understand all of the parts until you said the answer can be read directly off the index table.

    The only connection I get is this
     5ind_{5}x \equiv 6 \pmod{22} and
     x^5 \equiv 8 \pmod{23}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Paperwings View Post
    Opalg, I understand all of the parts until you said the answer can be read directly off the index table.

    The only connection I get is this
     5ind_{5}x \equiv 6 \pmod{22} and
     x^5 \equiv 8 \pmod{23}
    Pay no attention to my comment. I was being stupid. I was trying to solve 5^x\equiv8\!\!\!\pmod{23} rather than x^5\equiv8\!\!\!\pmod{23}.

    But if it's any help, I notice that 5\times 10 = 50\equiv6\!\!\!\pmod{22}, so you can take y=10.

    Edit ... and from the index table, that gives x=9, which works!! 3\times9^5 = 177147 = 1 + 23\times7702
    Last edited by Opalg; November 29th 2008 at 09:16 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2008
    Posts
    119
    Ah, thank you. I also got y = 10 and subsequently 9 although I used "guess-and-check"
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Lost in Mod Congruences
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 10th 2009, 02:04 PM
  2. [SOLVED] Quadratic Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 14th 2008, 09:43 PM
  3. [SOLVED] Linear Congruences - Classes of Solutions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 12th 2008, 09:04 AM
  4. question on distinct solutions to congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 17th 2008, 05:47 PM
  5. Replies: 0
    Last Post: March 21st 2007, 10:18 AM

Search Tags


/mathhelpforum @mathhelpforum