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$.

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

  • $\begingroup$ 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}$ ? $\endgroup$ – Sentient Aug 4 '17 at 23:33
  • $\begingroup$ CRT guarantees that this value is unique; since $r$ works, it must be the value. $\endgroup$ – platty Aug 4 '17 at 23:34
  • $\begingroup$ Ah, ok that would make sense. Thanks! $\endgroup$ – 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$.

  • $\begingroup$ 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}$. $\endgroup$ – Sentient Aug 4 '17 at 23:38
  • $\begingroup$ Yes. And $n_1^{-1}\bmod n_2\equiv u$, $n_2^{-1}\bmod n_1\equiv v$ $\endgroup$ – Bernard Aug 4 '17 at 23:43
  • $\begingroup$ Wait how were those general identities for $u$ and $v$ constructed? $\endgroup$ – Sentient Aug 4 '17 at 23:44
  • $\begingroup$ Do you mean the last ones? $\endgroup$ – Bernard Aug 4 '17 at 23:45
  • $\begingroup$ Yes, because extended Euclid works for specified values right? $\endgroup$ – Sentient Aug 4 '17 at 23:45

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.