# Special Case of Chinese Remainder Theorem

The Chinese Remainder Theorem states that if $n_1, n_2$ are coprime, and

$x = a_1 \pmod{n_1}$

$x = a_2 \pmod{n_2}$

then in the space of $\pmod{n_1n_2}$ there exists a unique $x$ given by

$x = a_1 n_2 (n_2^{-1} \pmod{n_1}) + a_2 n_1 (n_1^{-1} \pmod{n_2}) \pmod{n_1n_2}$.

In the proof of correctness for RSA, a special case of the Chinese Remainder Theorem is used where

$x = r \pmod{n_1}$

$x = r \pmod{n_2}$

and thus,

$x = r \pmod{n_1n_2}$.

How is

$x = r n_2 (n_2^{-1} \pmod{n_1}) + r n_1 (n_1^{-1} \pmod{n_2}) \pmod{n_1n_2}$

equivalent to

$x = r \pmod{n_1n_2}$?

I am not sure how to prove the general case of this without being given values of $n_1$ and $n_2$.

• The case $r=1$ is sufficient. Once you have that, you can simply multiply by general $r$ modulo $n_1 n_2$. – hardmath Aug 5 '17 at 3:23
• You need $(n_1,n_2)= 1$ for this to be true. – steven gregory Aug 5 '17 at 16:05
• $\gcd(n_1, n_2) = 1$ is true since $n_1$ and $n_2$ are coprime if that is what you are referring to. – Sentient Aug 5 '17 at 23:57

Not a full proof, but might provide some intuition: One way I like to think about CRT is that "if $\gcd(n_1,n_2) = 1$, then for any $a_1,a_2$, there is a unique $y \in \mathbb{Z}/n_1n_2\mathbb{Z}$ such that $y \equiv a_1 \pmod {n_1}$ and $y \equiv a_2 \pmod {n_2}$."

In this case, for $a_1 = a_2 = r$, we have $r \equiv r \pmod {n_1}$ and $r \equiv r \pmod {n_2}$, so we are done.

• But how does one go from $r \equiv r \pmod{n_1}$ and $r \equiv r \pmod{n_2}$ to $r \equiv r \pmod{n_1n_2}$ ? – Sentient Aug 4 '17 at 23:33
• CRT guarantees that this value is unique; since $r$ works, it must be the value. – platty Aug 4 '17 at 23:34
• Ah, ok that would make sense. Thanks! – Sentient Aug 4 '17 at 23:36

This is because the inverses modulo $n_i$ are obtained through a Bézout's identity: $$un_1+vn_2=1,$$ so that $x\equiv run_1+rvn_2=r\cdot 1\mod n_1n_2$.

• Walk me through this. So by definition of co-prime, $gdc(n_1, n_2) = 1$. Bezout's identity states that $u$ and $v$ exist such that $u n_1 + v n_2 = 1$. $u$ and $v$ can be found through extended Euclid's algorithm. And you're saying $u = n_1^{-1} \pmod{n_2}$ and $v = n_2^{-1} \pmod{n_1}$. – Sentient Aug 4 '17 at 23:38
• Yes. And $n_1^{-1}\bmod n_2\equiv u$, $n_2^{-1}\bmod n_1\equiv v$ – Bernard Aug 4 '17 at 23:43
• Wait how were those general identities for $u$ and $v$ constructed? – Sentient Aug 4 '17 at 23:44
• Do you mean the last ones? – Bernard Aug 4 '17 at 23:45
• Yes, because extended Euclid works for specified values right? – Sentient Aug 4 '17 at 23:45