Specializing general CRT formula to constant residue case

Question

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

Answer 1

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.

Answer 2

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