1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To prove the systems are equivalent you need to prove implications in both directions. $\endgroup$ – Bill Dubuque May 2 '17 at 23:39
  • $\begingroup$ @BillDubuque That wasn't the question. $\endgroup$ – B. Goddard May 3 '17 at 0:42
  • $\begingroup$ Sure it is, viz. "the reasoning behind this". $\endgroup$ – Bill Dubuque May 3 '17 at 0:58
  • $\begingroup$ @BillDubuque The "reasoning behind" the substitution. The substitution is one way. I feel like I'm back on sci.math. $\endgroup$ – B. Goddard May 3 '17 at 1:00
  • $\begingroup$ No, the crux of the matter is that it leads to an equivalent system, and this requires proof of both directions. $\endgroup$ – Bill Dubuque May 3 '17 at 2:49

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.