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

  • 1
    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.2011-02-25
  • 0
    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$2011-02-25
  • 0
    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.2011-02-25
  • 0
    @Arturo:http://www.wolframalpha.com/input/?i=ChineseRemainder[{4}%2C%20{3}]&t=ff3tb012011-02-25
  • 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).