Results 1 to 6 of 6

Math Help - Simultaneous equation

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    Simultaneous equation

    Hi, can anyone find what x and y are in the following two equations?

    (312x + y)mod676=361
    (461x + y)mod676=626

    The fact that mod is in there has threw me!

    Thanks

    P.S I think this is in the right forum? Its kind of number theory, but still just a simultaneous equation at the end of the day!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,865
    Thanks
    744
    Hello, sirellwood!

    If you don't understand modulo arithmetic,
    . . you should not be assigned this problem.


    \text{Solve: }\;\begin{array}{ccccc}312x + y &=& 361 & \text{(mod 676)} & [1] \\ 461x + y & \equiv & 626 & \text{(mod 676)} & [2] \end{array}

    Subtract [2] - [1]: . 149x \:\equiv\:265\text{ (mod 676)}


    We need the multiplicative inverse of 149\text{ (mod 676)}
    . . It took a while, but I found it: . 245


    Multiply by 245: . 245\cdot 149x \;\equiv\;245\cdot265 \text{ (mod 676)}

    . . . . . . . . . . . . . . 36,\!505x \;\equiv\;64,\!925\text{ (mod 676)}

    . . . . . . . . . . . . . . . . . . \boxed{x\;\equiv\;29\text{ (mod 676)}}


    Substitute into [1]: . 312(29) + y \;\equiv\;362\text{ (mod 676)}

    . . . . . . . . . . . . . . . . . 9,\!048 + y \;\equiv\;361\text{ (mod 676)}

    . . . . . . . . . . . . . . . . . . . . . . y \;\equiv\;\text{-}8687\text{ (mod 676)}

    . . . . . . . . . . . . . . . . . . . . . . \boxed{y \;\equiv\;101\text{ (mod 676)}}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,185
    Thanks
    404
    Awards
    1
    Quote Originally Posted by Soroban View Post
    We need the multiplicative inverse of 149\text{ (mod 676)}
    . . It took a while, but I found it: . 245
    I was stuck on this point as well. Is there no way to calculate this?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    I have a vague recollection of using the Extended Euclidean Algorithm to find the inverse?.... im sure soroban knows better than me though!.... I just end up using an online mod inverse calculator!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,242
    Thanks
    1795
    Hah! I beat Soroban here! Yes, use the division algorithm repeatedly.

    149 divides into 676 4 times with remainder 80: 80= 676- 4(149).

    80 divides into 149 once with remainder 69: 69= 149- 80.

    69 divides into 80 once with remainder 11: 11= 80- 69.

    11 divides into 69 6 times with remainder 3: 3= 69- 6(11).

    3 divides into 11 3 times with remainder 2: 2= 11- 3(3).

    2 divides into 3 once with remainder 1: 1= 3- 2.

    Now, from 2= 11- 3(3) we have 3- (11- 3(3))= 4(3)- 11= 1.

    From 3= 69- 6(11) we have 4(69- 6(11))- 11= 4(69)- 25(11)= 1.

    From 11= 80- 69, we have 4(69)- 25(80- 69)= 29(69)- 25(80)= 1.

    From 69= 149- 80, we have 29(149- 80)- 26(80)= 29(149)- 54(80)= 1.

    From 80= 676- 4(149), we have 29(149)- 54(676- 4(149)= 245(149)- 54(676)= 1.

    That is the same as saying that 245(149)= 1+ 54(676) so that 245(149)= 1 (mod 676).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,865
    Thanks
    744
    Hello, HallsofIvy!

    Great job!


    I used a very primitive algebraic approach.
    It may appeal to those of you who are not familiar with
    . . or are uncomfortable with modulo arithmetic.
    See what you think . . .


    We have: . 149x \:\equiv\:265\text{ (mod 676)}

    We want \,a, the multiplicative inverse of 149 so that: . 149a \:\equiv 1\text{ (mod 676)}


    We have: . 149a \:=\:676b + 1

    . . a \:=\:\dfrac{676b + 1}{149} \:=\:4b + \dfrac{80b+1}{149} .[1]


    Since \,a is an integer, 80b + 1 must be a multiple of 149.

    . . 80b + 1 \:=\:149c \quad\Rightarrow\quad b \:=\:\dfrac{149c-1}{80} \:=\:c + \dfrac{69c - 1}{80} .[2]


    Since \,b is an integer, 69c - 1 must be a multiple of 80.

    . . 69c - 1 \:=\:80d \quad\Rightarrow\quad c \:=\:\dfrac{80d + 1}{69} \:=\:d + \dfrac{11d+1}{69} .[3]


    Since \,c is an integer, 11d + 1 must be a multiple of 69.

    . . 11d + 1 \:=\:69e \quad\Rightarrow\quad d \:=\:\dfrac{69e-1}{11} \:=\:6e + \dfrac{3e-1}{11} .[4]


    Since \,d is an integer, 3e - 1 must be a multiple of 11.
    . . But we can "eyeball" this equation: . e = 4


    Substitute into [4]: . d \:=\:6(4) + \dfrac{3(4)-1}{11} \:=\:25

    Sustitute into [3]: . c \:=\:25 + \dfrac{11(25)+1}{69} \:=\:29

    Substitute into [2]: . b \:=\:29 + \dfrac{69(29) - 1}{80} \:=\:59

    Substitute into [1]: . a \:=\:4(59) + \dfrac{80(59) + 1}{149} \:=\:245


    Therefore, 245 is the multiplicative inverse of 149\text{ (mod 676)}.


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


    Check


    (245)(149) \:=\:36,\!505 \:=\:54(676) + 1

    Therefore: . (245)(149) \:\equiv\:1\text{ (mod 676)}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simultaneous equation
    Posted in the Algebra Forum
    Replies: 19
    Last Post: September 30th 2011, 10:11 AM
  2. Simultaneous equation
    Posted in the Algebra Forum
    Replies: 11
    Last Post: May 15th 2011, 12:33 PM
  3. simultaneous equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 20th 2009, 06:52 AM
  4. Simultaneous equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 15th 2009, 05:07 AM
  5. Simultaneous Equation Help Please!
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 15th 2008, 12:22 PM

Search Tags


/mathhelpforum @mathhelpforum