Results 1 to 7 of 7

Math Help - Congruence Problem

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Congruence Problem

    Hi, I need to solve this congruence.

    7^x \equiv 6 (mod17)

    In the question, it has a squiggly line at the top of the congruence sign, but i'm not sure what that means .

    I know this questions probably has something to do with primitive roots, but I really dont know how to start.

    Please help.
    Katy
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Brute force

    Just multiply. Listing the powers of 7 mod 17 gives:
     7^1 \equiv 7 (mod 17)
     7^2 = 7*7 = 49 \equiv 15 (mod 17)
     7^3 \equiv 7*15 \equiv 3 (mod 17)
    etc. If my remainders are correct, the list of remainders with increasing powers of 7 are:
    7,15,3,4,11,9,12,16,10,2,14,13,6,...,
    so
      7 ^ {13} \equiv 6 (mod 17)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Ahh ok cool. Thank you

    Is this the only way of solving this congruence? What if x was really large? this could take a long time.

    And do you know what the wiggley line means at the top of the congruence sign? I didn't know how to write it in the math code. lol.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    A congruence sign is often written as an equals sign with a wiggly line on top of it. Another way is the 3 line equal sign you see here.

    Yes, if x is large it could take a long time. However this is very simple to program onto a computer.

    There are some shortcuts. For example, writing
    15 \equiv {-2} (mod 17)
    keeps the numbers smaller.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by harkapobi View Post
    Ahh ok cool. Thank you

    Is this the only way of solving this congruence? What if x was really large? this could take a long time.

    And do you know what the wiggley line means at the top of the congruence sign? I didn't know how to write it in the math code. lol.
    You will only have quadratic residues from 1 to 16.
    They are cyclic.
    Add a multiple of 16 to the x=13 above.
    ALL of the residues in that quantity will be cyclic.
    You then need to examine a max of 16 residues to find the result.

    7^{2199485} = 7^{13} \cdot 7^{2199472} \equiv 6 \mod 17
    .
    Last edited by aidan; November 18th 2009 at 12:07 PM. Reason: added example
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Thanks for all the help, but is there no easier way of solving this? I have another question that is similar you see,

    19^x \equiv17(mod22)

    and in the question I am told that 7 is a primitive root mod 22. So i'm assuming I need to use this somehow.

    Is the only way to solve this trial and error like above?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    One shortcut

    I'd also like to learn how to use a primitive root to help this calculation.

    However, your problem is really simple. Note 19 = -3(22) and 17 = -5(22). The powers of -3 are -3, 9, -27. Note -27 = -5(22). So your x=3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 29th 2011, 08:41 AM
  2. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 2nd 2009, 11:24 AM
  3. congruence problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 21st 2009, 01:22 PM
  4. Another congruence problem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 3rd 2009, 06:14 PM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum