Results 1 to 2 of 2

Math Help - Solve a Congruence

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    Solve a Congruence

    Please help with this problem:

    49x is congruent to 4000 (mod 999).

    I need to solve for x, and I can't figure out how to work it. Trying to use the Euclidean Algorithm.

    Thanks all!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2010
    Posts
    13
    Quote Originally Posted by meggnog View Post
    Please help with this problem:

    49x is congruent to 4000 (mod 999).

    I need to solve for x, and I can't figure out how to work it. Trying to use the Euclidean Algorithm.

    Thanks all!
    To begin with one can notice the following:

    4000 = 4*999 + 4 ≡ 4 (mod 999)

    So, we've reduced the problem to 49x ≡ 4 (mod 999)

    Now, by Euclid's algorithm

    999 = 20*49 + 19
    49 = 2*19 + 11
    19 = 11 + 8
    11 = 8 + 3
    8 = 3*3 - 1

    Going backwards in the algorithm you'll get the following

    1 = 367*49 - 18*999 ≡ 367*49 (mod 999)

    with other words: the inverse of 49 in Z_999 is 367

    So,

    49x ≡ 4 (mod 999)

    367*49x ≡ 367*4 (mod 999)

    x ≡ 367*4 = 1468 = 999 + 469 ≡ 469 (mod 999)

    x ≡ 469 (mod 999)

    and that's it!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solve linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 23rd 2010, 04:50 AM
  2. Solve quad congruence
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 19th 2009, 06:54 AM
  3. How do I solve this congruence?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 09:08 PM
  4. congruence [I have no idea how to solve this]
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2008, 05:55 PM
  5. Solve the Quadratic Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 05:13 PM

Search Tags


/mathhelpforum @mathhelpforum