# Why Chinese Remainder Theorem(CRT) will give unique $x \bmod M$?

If the $$m_1, ..., m_r$$ are pairwise coprime, and if $$a_1, \ldots, a_r$$ are any integers, then system of $$r$$ conqruences

$$x \equiv a_ i \bmod m_ i \text{( 1\le i \le r)}$$

has a unique solution modulo $$M= m_1 * m_2*....m_r$$, which is given by

$$x=\Sigma_{i=1}^{r}\space a_iM_i y_i \bmod M,$$

where $$M_i = \frac{M}{m_i}$$ and $$y_i =M_i^{-1} \bmod m_i$$ for $$1\le i \le r$$.

Could you please explain CRT will give unique $$x \bmod M$$?

## migrated from crypto.stackexchange.comMar 28 at 17:39

This question came from our site for software developers, mathematicians and others interested in cryptography.

• Because .... that's what the statement of CRT claims???? Go through the proof of CRT. That will tell you why the CRT is true. – fleablood Mar 28 at 19:55

The existence of a unique solution follows directly by considering the kernel of the natural map $$\mathbb Z \to \mathbb Z / m_1 \mathbb Z \times \cdots \times \mathbb Z / m_r \mathbb Z$$ given by $$x \mapsto (x \bmod m_1, \dots, x \bmod m_r)$$

Let x, y be integers both satisfying all those congruences.

Then $$x\equiv a_i\equiv y\pmod {m_i}$$ for every $$i$$.

Hence, $$m_i$$ divides $$x-y$$ for every $$i$$.

Since $$m_1,\dots, m_r$$ are pairwise coprime then...

Try to fill the gap.