Are There Multiple Solutions to this System of Linear Congruences?

[oliver$]

the system:

24x + 11y= 4 (mod 35)
5x + 7y= -13 (mod 35)

is solved to get:

-113y= 111 (mod 35)
113x= 171 (mod 35)

which gives: (17,8).

should there not be more solutions?

 

[robert Ihnot]

No, with two unknowns, x and y, we need exactly two linear equations to find the unique solution. Now, if x or y was quadratic, it would be different.

You can see from your own work that, we use one of the equations to eliminate one of the terms. Thus what remains is all in one unknown.

However, since it is a modulo equation, you can add or subtract any multiple of 35 to x or y.

 

[shmoe]

You might want to check your solution by substituting it back into the original equations.

 

[Hurkyl]

Ask yourself two questions:

(1) Why do you think there should be more solutions?
(2) What things do you know about solutions to systems of linear equations?

When answering these questions, it might help to consider things mod 7 and mod 5, so that you're working over a field (and thus most of what you learned in linear algebra is applicable)

 

[robert Ihnot]

Oliver$: should there not be more solutions?

Unfortunately "Yes," since there is a mistake in your value for y.

It might be easier as Hurkyl suggests to work with modulo 5 and modulo 7.

 

[ascheras]

ok, upon doing it (mod 7) and (mod 5), i got (3,4) (mod 7) and (1,2) (mod 7). does that sit well? or should i now apply the CRT?

 

[shmoe]

ok, upon doing it (mod 7) and (mod 5), i got (3,4) (mod 7) and (1,2) (mod 7). does that sit well? or should i now apply the CRT?

You can use the CRT after, but you might want to check your (1,2) answer mod 5 (I assume that's your mod 5 solution).

 

[ascheras]

sorry, i meant (2,1).