Simultaneous equation

**sirellwood** · March 6th 2011, 05:22 PM

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!

**Soroban** · March 6th 2011, 06:25 PM

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

**topsquark** · March 6th 2011, 06:46 PM

Originally Posted by Soroban

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

**sirellwood** · March 6th 2011, 07:16 PM

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!

**HallsofIvy** · March 7th 2011, 03:05 AM

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

**Soroban** · March 7th 2011, 05:08 AM

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

Thread: Simultaneous equation

LinkBack

Thread Tools

Display