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$

1 Answer 1

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$
10
  • $\begingroup$ To prove the systems are equivalent you need to prove implications in both directions. $\endgroup$ May 2, 2017 at 23:39
  • $\begingroup$ @BillDubuque That wasn't the question. $\endgroup$
    – B. Goddard
    May 3, 2017 at 0:42
  • $\begingroup$ Sure it is, viz. "the reasoning behind this". $\endgroup$ May 3, 2017 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, 2017 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$ May 3, 2017 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.