Results 1 to 5 of 5

Thread: a modular linear equation

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    4

    a modular linear equation

    Hello,

    I have to solve this modular linear equation (in paper not using programming)

    18x = 81 (mod171)

    My thought is we begin using the extended euclidean algorithm (ax+by=gcd(a,b) calculating : (div a/b), the gcd(a,b) and the x,y

    An Example Using the Extended Euclidean Algorithm

    I know this isn't a short exercise so thanks in advance for looking and trying to help. Meanwhile I'm doing my best searching & trying to understand.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by octagonreturns View Post
    Hello,

    I have to solve this modular linear equation (in paper not using programming)

    18x = 81 (mod171)

    My thought is we begin using the extended euclidean algorithm (ax+by=gcd(a,b) calculating : (div a/b), the gcd(a,b) and the x,y

    An Example Using the Extended Euclidean Algorithm

    I know this isn't a short exercise so thanks in advance for looking and trying to help. Meanwhile I'm doing my best searching & trying to understand.
    First of all, divide by 9 :

    $\displaystyle 18x=81 \mod 171 \Longleftrightarrow 18x=81+171k$

    It yields $\displaystyle 2x=9+19k$

    So you want to solve for x in $\displaystyle 2x=9 \mod 19$

    Now, use the Euclidian algorithm, to find u and v such that $\displaystyle 2u+19v=1 \longleftrightarrow 2u=1 \mod 19$ (this is possible because 2 and 19 are coprime)
    Then, we'll multiply by 9 to get : $\displaystyle 2x=9 \mod 19$, where x=9u.

    ---------------------

    $\displaystyle 19=2*9+1 \rightarrow 1=19+2*(-9)$

    So u=-9

    Hence $\displaystyle x=-81=\boxed{14} \mod 19$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    confused.

    Where did the 14 come from in the final answer??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by duggaboy View Post
    Where did the 14 come from in the final answer??
    $\displaystyle -81 = 19 \times (-5) + 14$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by octagonreturns View Post
    18x = 81 (mod171)
    Note that $\displaystyle \gcd(18,171)=9$.

    If we can find a solution $\displaystyle x_0$ then all other solutions (in different congruence classes) shall be given by $\displaystyle x_0 + t\cdot \tfrac{171}{9} = x_0+ 19t$ whete $\displaystyle 0\leq t\leq 8$. It remains to find a solution $\displaystyle x_0$. You can do what Moo did to get $\displaystyle x_0 = 14$. Thus, the other solutions are given by $\displaystyle 14,33,52,71,90,109,128,147$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 1st 2009, 11:16 AM
  2. Replies: 1
    Last Post: Nov 17th 2008, 06:17 PM
  3. Modular help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 5th 2007, 11:53 AM
  4. Modular Arithmetic - Simultaneous Equation
    Posted in the Advanced Math Topics Forum
    Replies: 6
    Last Post: Apr 28th 2005, 08:52 AM

Search Tags


/mathhelpforum @mathhelpforum