System of Simultaneous Congruences

[Korg]

Homework Statement

Solve the following system of simulataneous congruences:

2X+3Y = 2(mod 5)
X+2Y = 3 (mod 5)
X+2Y = 3 (mod 7)
4X+3Y = 4 (mod 7)

Homework Equations

The Attempt at a Solution

I know how to solve a similar problem if there was just one variable, using the Chinese remainder theorem but I'm not quite sure how to adapt it here. I know the CRT is applicable since 5 and 7 are coprime.

I started trying to solve it by using the two X+2Y congruences and got that X+2Y = 3 (mod 35) . but I'm not sure if this even helps to solve the whole system.
Can anyone help at all?

 

[511201]

I think, you can solve the first 2 equations, which gives
X=0 (mod 5)
Y=4 (mod 5)
and then the 3rd and 4th.. which gives
X=4 (mod 7)
Y=3 (mod 7)

And, then solve X=0(mod 5) and X=4(mod 7), which would give X=25 (mod 35)
similarly for Y, you should get Y=24 (mod 35)

By the way, are you studying at Warwick university?

 

[Korg]

Thanks a lot, i get it now. I just wasnt sure how to handle it with 2 variables and then realized you can just treat it as a normal simultaneous equation when you're working with the same modulo.
And yes i do, you've found me out haha

 

[511201]

lol! haha..
Im studying at Warwick too!
Just let me know if my answer is right or not, after u solve it.. coz, I'm not sure if I've made any careless mistakes in between..

 

[Korg]

I got exactly the same answer, so hopefully it's right!

 

[Borgash]

hey I got same answer too, problem I am having is solving the second set of equations

X+2Y = 3 (mod 7)
4X+3Y = 4 (mod 7)

I know the answer I want but the matrix I make to get this answer gives me the wrong solutions, does anyone have any help to do this? I can do the rest of the problem easily and get the same answer as you guys I just can't see where I am going wrong on this part

 

[511201]

I think, you can multiply equation 1 by 3 and then subtract it from 2, which will give you a value for Y, and then substitute in any of the equations to get X

 

[Borgash]

ah yeah thanks that does work but i find the matrix method to be better as technically multiplying the first equation by 4 should give me 4X + 8Y = 12mod28

as if a = bmod(m) then na = nbmod(nm) which whilst your way does give the correct answer I am not sure its technically right as I did do that in the first place but then wondered about if it was actually true

i used a matrix method which worked for the first set but on this one my matrix just doesn't work, i need the det to be 1 diffrent than it is but maybe I can skip that and say by the method used in step one

 

[511201]

hey
how do we use matrices to solve these? Ax=b?

Well, what I did was:
3X+6Y=9+21m
4X+3Y=4+7n
Adding them gives:
7X+9Y=13+7(3m+n)
9Y=13+7(3m+n-X)
9Y= 13 (mod 7)
9Y= 6 (mod 7)
So, Y=3 (mod 7)

Please let me know if the above is right or wrong, and also if the matrix method is more sophisticated...thnx

 

[Borgash]

yeah your way works, you wouldn't need 9Y either you could just put 2Y as 9 = 2mod7

the matrix way is [a b
~~~~~~~~~~~c d] [X,Y]^T = [ e f] ^T (sorry for the ~ had to make the matrix line up)

where aX + bY = emodn
cX + dY = fmodn

then you just multiply the left hand sade with the left inverse of the 2x2 matrix to find X, Y

worked for me in the first case fine but something went wrong in the second case, I think it is more sophisticated and definitely helps when you have more than 2 equations or 2 variables however I seem to have made a mistake in my second matrix for the mod7 part but I can't figure out where, works perfectly and easily for the first part

 

[511201]

for the 2nd part (using matrices)
(X, Y) = (-1/5, 8/5)
So, 5X=-1 mod 7
5X=6 mod 7, hence X=4 mod 7
Similarly for Y
5Y=8 mod 7=1 mod 7
So, Y=3 mod 7
So, it does work and is definitely more sophisticated! :)

 

[Borgash]

ah yeah thanks i had tried to convert the determinant into mod7 instead, easier to not do that it turns out, cheers :)