Congruence equal to zero in chinese remainder theorem

1.2k Views Asked by At

Congruence equal to zero in chinese remainder theorem

When there is a congruence equal to zero in the chinese remainder theorem, this congruence will not appear in the solution because of the factor $0$. See example! But the modulus of that congruence is still part of M.

But what if the modulus of that congruence is not pairwise relative prime. Can we than also use the chinese remainder theorem?

I should say no, because we can only apply the chinese remainder theorem if all the moduli are pairwise relative prime. But this is a special case...

enter image description here

1

There are 1 best solutions below

3
On

As you are saying,

we can only apply the chinese remainder theorem if all the moduli are pairwise relative prime

When the moduli are not pairwise relative prime, for e.g. in your photo, the modulus 10 and modulus does have a common divisor 2>1, so Chinese remainder theorem is not directly applicable in this case.

However, observe that$$x\equiv0\space(mod\space15)\Leftrightarrow x\equiv0\space(mod \space3) \space and \space x\equiv0\space(mod\space5)[Do\space you\space know\space why?] $$
Therefore, we can substitute the equivalent equations into the system of moduli equation, and similarly, we can break$$x\equiv9\space(mod\space10)$$into$$x\equiv9\space(mod\space2)$$and$$x\equiv9\space(mod\space5)$$ So unfortunately there is a contradiction about mod 5, so the equation is not solvable, while as actually, when Chinese Remainder Theorem applies, there must be a class of solution mod something.

p.s.Usually, we can actually combine same equation and make the system of linear congruence equations into a form which the Chinese Remainder Theorem applies

By the way, as a I am typing this answer to the end, I finally realise that what you are going wrong is a typo in the initial system of equations, I think '15' should be '13'?