Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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 –  Quixotic 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
add comment

1 Answer

up vote 2 down vote accepted

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.