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.com Mar 28 at 17:39

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

  • 2
    $\begingroup$ Because .... that's what the statement of CRT claims???? Go through the proof of CRT. That will tell you why the CRT is true. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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