1
$\begingroup$

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!"

  • 0
    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 sols2011-02-25

1 Answers 1

2

The author believes that things can only equal 0, 1, or 2 mod 3 and nothing can be equal to 4 mod 3. Others would accept that 1 and 7 equal 4 mod 3 (and might use the equivalence sign instead of the equals sign).