# Thread: Simultaneous equation

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!

2. 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)}}$

3. Originally Posted by Soroban
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

4. 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!

5. 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).

6. 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)}$