Results 1 to 6 of 6

Thread: Simultaneous equation

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    184
    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
    12,028
    Thanks
    849
    Hello, sirellwood!

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


    $\displaystyle \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]: .$\displaystyle 149x \:\equiv\:265\text{ (mod 676)}$


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


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

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

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


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

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

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

    . . . . . . . . . . . . . . . . . . . . . .$\displaystyle \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
    11,163
    Thanks
    736
    Awards
    1
    Quote Originally Posted by Soroban View Post
    We need the multiplicative inverse of $\displaystyle 149\text{ (mod 676)}$
    . . It took a while, but I found it: .$\displaystyle 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
    184
    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
    19,798
    Thanks
    3035
    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
    12,028
    Thanks
    849
    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: .$\displaystyle 149x \:\equiv\:265\text{ (mod 676)}$

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


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

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


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

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


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

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


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

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


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


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

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

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

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


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


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


    Check


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

    Therefore: .$\displaystyle (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: Sep 30th 2011, 09:11 AM
  2. Simultaneous equation
    Posted in the Algebra Forum
    Replies: 11
    Last Post: May 15th 2011, 11:33 AM
  3. simultaneous equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Sep 20th 2009, 05:52 AM
  4. Simultaneous equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Sep 15th 2009, 04:07 AM
  5. Simultaneous Equation Help Please!
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Apr 15th 2008, 11:22 AM

Search Tags


/mathhelpforum @mathhelpforum