Thread: Trouble solving a system of linear congruences.

Hi all,

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,
m

The congruence has a solution if and only if d=gcd(a,m) divides b. The solution is given by . That much I know. And I see you have put the system into upper triangular form, which is probably a good idea.

One idea is to break the modulus down to powers of primes (in your case 228=4*3*19) and solve for each modulus, then use the Chinese Remainder Theorem to get the final solution. I haven't worked out what happens for your system.

I would just work backward through the equations (as you did):



, since gcd(226,228)=2. Or,

where z=0 or 1. Now the next equation up:





(z dropped out of the equation, otherwise we would treat it like a constant)

where w=0,1, or 2. So that gives us six solutions. But there is another equation:

Since gcd(224,228)=4 and gcd(225,228)=1, substitute for y:





and since gcd(224,228)=4 must divide 142-114z, we must have z=1.

Now substitute for x:



and only w=1 works. So only the solution z=1, w=1 is valid, so the solution is:




- Hollywood

It does work to break down the modulus into powers of primes and solve 3 systems of congruences:

224x + 225y = 226 (mod 228)
3x + 6y = 153 (mod 228)
0x + 226y = 132 (mod 228)

The three systems are:

0x + 1y = 2 (mod 4)
3x + 2y = 1 (mod 4)
0x + 2y = 0 (mod 4)
solution: x=3, y=2 (mod 4)

2x + 0y = 1 (mod 3)
0x + 0y = 0 (mod 3)
0x + 1y = 0 (mod 3)
solution: x=2, y=0 (mod 3)

15x + 16y = 17 (mod 19)
3x + 6y = 1 (mod 19)
0x + 17y = 18 (mod 19)
solution: x=12, y=10 (mod 19)

And applying the CRT gives the solution.

- Hollywood

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.

Thanks again,
m