Trouble solving a system of linear congruences.
I have three related linear congruences, described below, and I'm trying to solve for x and y.
224x + 225y = 226 (mod 228)
3x + 6y = 153 (mod 228)
0x + 226y = 132 (mod 228)
The trouble I'm having is that these can have multiple solutions and I don't know of a good way to determine which ones to use without calculating all of them.
For example, 226y = 132 (mod 228) has two solutions, y=48 and y=162.
The second equation (3x + 6y = 153 mod 228) will have three solutions for x regardless of which of the values for y is chosen (x=31, x=107, x=183). However, the first equation (224x + 225y = 226 mod 228) has no solution for x when y=48 and has 4 solutions when y=162 (x=50, x=107, x=164, x=221).
After having calculated all of the combinations, I can tell by looking at it that y=162 (because y=48 doesn't solve the first congruence) and that x=107 (because it is common in the solutions for both the first and second congruence.
Is there a formula I can apply to determine which solutions to use for any particular congruence, given the related congruences? Maybe some way to calculate them all simultaneously? While calculating solutions for all of the combinations worked out in this case, I don't think it is practical when the number of unknowns increases. I started with five unknowns across six congruences but used matrix reduction to get it down to this.
I'm a computer science major without a very strong number theory background and I'm not even sure what to call the problem I'm trying to solve, which makes it difficult to search for on the internet (though I've tried) or to find what sections of math books might be related (though I've scoured the local book stores). Any help would be appreciated.
Thank you for your time,
Thanks Hollywood, I hadn't considered CRT.
Thanks Hollywood for spotting that.
I was looking into calculating an inverse matrix and using that to coordinate the different congruences, but I was worried because not all matrices have an inverse. I'll try coding your method up and seeing if there are any cases in which it does not work.