Is Chinese Remainder Theorem a double implication?

118 Views Asked by At

I mean, if you have multiples equations and all modulus are co-primes you can 'merge' them in just one equation.

But can you do it reversed? Something like:

(a mod p*q) p and q co-prime

And then create the equations (a mod p) and (a mod q). I've seen that:

18≡18(mod 35) but

18≡4(mod 7) and 18≡3(mod 5)

But I've seen other questions where it was told that you are able to do it.

2

There are 2 best solutions below

1
On BEST ANSWER

This direction of the statement is trivially true.

If $x \equiv a \pmod {pq}$, then $pq \mid (x-a)$.

So $p \mid (x-a) $ and $q \mid (x-a)$.

So, $x \equiv a \pmod p$ and $x \equiv a \pmod q$.

0
On

(Too long for a comment)

I think your original doubt came from a common misunderstanding about notation. $$x \equiv a \pmod {n}$$ does not mean that $x$, reduced modulo $n$, equals $a$. It means that the difference between $a$ and $x$ is a multiple of $n$, or, to look at it another way, that $a$ reduced modulo $n$ and $x$ reduced modulo $n$ are equal.

It is true that $13 \equiv -478847 \pmod {10}$, for example.