# Solving systems of linear congruences (modular equations)

This is a task from an old programming contest the task is as follows, A list of system of linear equations is given in the inputs.If the system is solvable we have to output the solution in the form of 'A + Bk',else we have to output "no solutions".

Now lets consider the inputs:

x = 3 (mod 4)

x = 4 (mod 3)

x = 1 (mod 2)
x = 2 (mod 3)
x = 3 (mod 4)
x = 4 (mod 5)
x = 5 (mod 6)
x = 0 (mod 7)

x = 2 (mod 2)
x = 4 (mod 3)
x = 6 (mod 5)
x = 8 (mod 7)
x = 10 (mod 11)


Using Chinese remainder theorem,I guess the outputs should be:

3 + 4k
1 + 3k
119 + 420k
736 + 2310k


But according to the Judges I/O the output is :

3 + 4k
no solutions
119 + 420k
no solutions


Now I can see many had solved this task could anybody explain how this output holds valid for the inputs?

PS:There is a note from the problem author that "Not all are solvable using the Chinese Remainder Theorem, and some aren't solvable at all!"

-
The Chinese Remainder Theorem applies directly when the moduli are pairwise coprime. So for example, your second system needs to be adjusted before you can apply CRT, because the moduli are not pairwise coprime. – Arturo Magidin Feb 25 '11 at 16:17
Please give a link to the contest's problem page. Perhaps they are using a different definition of mod. For instance, your answer $3k+1$ for second problem is correct for $x = 4 \mod 3$ – Aryabhata Feb 25 '11 at 16:18
It would seem that for some strange reason they are considering $x\equiv 4\pmod{3}$ to be "unsolvable". Maybe they are considering the equation as giving the remainder when dividing by the modulus, in which case $4$ is not a valid remainder when dividing by $3$. The same reasoning would apply to the fourth system, since three of the congruences involve "remainders" that are larger than the moduli. – Arturo Magidin Feb 25 '11 at 16:19
@Arturo:wolframalpha.com/input/?i=ChineseRemainder[{4}%2C%20{3}]&t=ff‌​3tb01 – VelvetThunder Feb 25 '11 at 16:20
One can transform a system of congruences such as your third system into one for which the Chinese Remainder Theorem applies; the point is that it does not apply directly. For instance, you could take $x\equiv 5\pmod{6}$ and break it up into $x\equiv 5\pmod{3}$ and $x\equiv 5 \pmod{2}$ (using the CRT), then compare to the congruences you already have to see if they are compatible; if so, you keep the one that implies the other; if not, there is no solution. But you cannot apply CRT directly (and by "apply" I mean apply, not type it into a black-box webpage that spits out sols – Arturo Magidin Feb 25 '11 at 16:23