Chinese remainder theorem method

Question

I am given an iterative method to solve a system using the Chinese remainder theorem, but there is one step of which I don't understand the reason.

We have a system of congruences \begin{cases} x\equiv a_{1} \mod n_{1} \\ x \equiv a_{2} \mod n_{2} \\ ...\\x \equiv a_{k} \mod n_{k}\end{cases}that meet the requirements for the Chinese remainder theorem ($n_{1},...,n_{k} \in \mathbb{N}_{0}$ and $gcd(n_{i},n_{j})=1$ for $i \neq j$). (1) Find $\lambda_{1}, \lambda_{2}$ so that $\lambda_{1} n_{1}+ \lambda_{2} n_{2} = 1$. This is possible by the theorem of Bézout-Bachet because $gcd(n_{1},n_{2})=1$. (2) Now, replace the first two congruences \begin{cases} x\equiv a_{1} \mod n_{1} \\ x \equiv a_{2} \mod n_{2} \end{cases} by $x \equiv a_{2} \lambda_{1} n_{1} + a_{1} \lambda_{2} n_{2} \mod n_{1} n_{2}$. (3) Repeat this until you are left with only one equation.

My question: How do you get to the replacement in step 2? What is the reasoning behind this?

Answer 1

If you have $$x\equiv a_2\lambda_1 n_1+ a_1\lambda_2 n_2 \pmod{n_1n_2},$$ then you certainly have

$$x\equiv a_2\lambda_1 n_1+ a_1\lambda_2 n_2 \pmod{n_1},$$

which reduces to

$$x\equiv a_1\lambda_2 n_2 \pmod{n_1},$$

You can replace $\lambda_2 n_2$ by $1$ in this last congruence by reducing

$\lambda_1 n_1 + \lambda_2 n_2 =1$ modulo $n_1$ to get $ \lambda_2 n_2 \equiv 1 \pmod{n_1}.$ So you have $x \equiv a_1 \pmod{n_1}$. Likewise for the other subscript.