Results 1 to 8 of 8

Math Help - Simultaneous equations with a modulus

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    4

    Simultaneous equations with a modulus

    Hi, Im have trouble figuring out how to solve simultaneous equations of the form:

    4a + b (mod 26) = 20
    19a + b (mod 26) = 25

    I know how to do simultaneous equations normally but with the modulus I keep messing up somewhere.

    I multiplied everything in the top equation by + 1 and everything in the bottom equation by -1 to get:

    4a + b (mod 26) = 20
    -19a - b (mod 26) = -25

    then add them to get:
    -15a = -5

    It seems obvious to me that Im doing something wrong but I've had trouble finding out how to do this properly. Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Slimbiggins View Post
    Hi, Im have trouble figuring out how to solve simultaneous equations of the form:

    4a + b (mod 26) = 20
    19a + b (mod 26) = 25

    I know how to do simultaneous equations normally but with the modulus I keep messing up somewhere.

    I multiplied everything in the top equation by + 1 and everything in the bottom equation by -1 to get:

    4a + b (mod 26) = 20
    -19a - b (mod 26) = -25

    then add them to get:
    -15a = -5

    It seems obvious to me that Im doing something wrong but I've had trouble finding out how to do this properly. Thank you.
    So you have

    -15a \equiv -5 \mod(26) \iff 15a \equiv 5 \mod(26)

    Now use the euclidean alogrithm to find 15 inverse mod 26

    You should get 7

    This gives

     7\cdot 15a \equiv 7 \cdot 5 \mod(26)  \iff a \equiv 35 \mod(26) \iff a \equiv 9 \mod(26)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by Slimbiggins View Post
    Hi, Im have trouble figuring out how to solve simultaneous equations of the form:

    4a + b (mod 26) = 20
    19a + b (mod 26) = 25

    I know how to do simultaneous equations normally but with the modulus I keep messing up somewhere.

    I multiplied everything in the top equation by + 1 and everything in the bottom equation by -1 to get:

    4a + b (mod 26) = 20
    -19a - b (mod 26) = -25

    then add them to get:
    -15a = -5

    It seems obvious to me that Im doing something wrong but I've had trouble finding out how to do this properly. Thank you.
    Hi slimbiggins! welcome to the forum.
    here we go:

    first congruence:



    substitute this in the second to get:

    .

    The last one is a linear congruence. You must know how to solve that. can you see what to do from here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2011
    Posts
    4
    Quote Originally Posted by TheEmptySet View Post
    So you have

    -15a \equiv -5 \mod(26) \iff 15a \equiv 5 \mod(26)

    Now use the euclidean alogrithm to find 15 inverse mod 26

    You should get 7

    This gives

     7\cdot 15a \equiv 7 \cdot 5 \mod(26)  \iff a \equiv 35 \mod(26) \iff a \equiv 9 \mod(26)
    Thank you, that was very clear but I not sure about how you got the multiplicative inverse. I thought the euclildean algorithm finds the gcd of two numbers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Slimbiggins View Post
    Thank you, that was very clear but I not sure about how you got the multiplicative inverse. I thought the euclildean algorithm finds the gcd of two numbers.
    See post number #3 here to see how it is done

    http://www.mathhelpforum.com/math-he...tml#post646421

    If does but if they are corpime then youcan express 1 as a linear combination 15 and 26

    a\cdot 26 +b \cdot 15 =1 now if you mod out by 26 you get

    b\cdot 15 \equiv 1 \mod{26} so b must be 15 inverse.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2011
    Posts
    4
    Quote Originally Posted by TheEmptySet View Post
    See post number #3 here to see how it is done

    http://www.mathhelpforum.com/math-he...tml#post646421

    If does but if they are corpime then youcan express 1 as a linear combination 15 and 26

    a\cdot 26 +b \cdot 15 =1 now if you mod out by 26 you get

    b\cdot 15 \equiv 1 \mod{26} so b must be 15 inverse.
    Sorry, I'm having trouble understanding this. I looked at the other post but couldn't figure out where everything was coming from.
    I looked at some other tutorials and was equally confused. I know how to do the extended euclidean alogrithm but in your post and
    the other tutorials it looks very different from the way I was shown how to do it. Everything else made perfect sense but getting the
    inverse has me stumped.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    okay so you want to find 15 inverse mod 26

    So you start with 26 and divide it by 15 to get

    26=1\cdot 15+11 \iff 11 = 26-1\cdot 15

    15=1\codt 11 +4 \iff 4 = 15 -1\cdot 11

    11=2\cdot 4+3 \iff 3 =11 -2\cdot 4

    4 = 1\cdot 3+1

    Now that we have the remainder of 1 we want to express it in terms of 26 and 15.
    we back substitute to work our way back to the top.

    1 = 4 - 1\cdot 3

    1 = 4-1(11-2\cdot 4)=-1\cdot 11+3\cdot 4

    1= -1\cdot 11+3(15 -1\cdot 11)=3\cdot 15-4\cdot 11

    1 = 3\cdot 15-4\cdot (26-1\cdot 15)=7\cdot 15-4\cdot 26

    So now we have 1 as a linear combination of 15 and 26

    1 = 7\cdot 15-4\cdot 26

    so we can see that 15 inverse is 7
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2011
    Posts
    4
    Thanks for all your help, I understand it now. Thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simultaneous Equations 4 variables, 4 equations
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: December 7th 2011, 05:06 PM
  2. Simultaneous equations
    Posted in the Algebra Forum
    Replies: 10
    Last Post: January 10th 2010, 05:21 AM
  3. Replies: 3
    Last Post: February 27th 2009, 08:05 PM
  4. Replies: 7
    Last Post: April 15th 2008, 03:05 PM
  5. Modulus and Irrational Equations
    Posted in the Algebra Forum
    Replies: 5
    Last Post: April 15th 2008, 05:42 AM

Search Tags


/mathhelpforum @mathhelpforum