Okay, so we have the Chinese Remainder Theorem:

If $m_1$ and $m_2$ are coprime then the simultaneous congruences $\left( x \equiv a_1 \mod m_1 \right)$, $\left( x \equiv a_2 \mod m \right)$ have a unique solution $\left(\mod m_1 m_2 \right)$.

I want to prove the solution for more than two congruences using the Chinese Remainder Theorem:

$x = \left[\Sigma_{i} {a}_i \frac {\Pi_{i} n_i} {n_i} \left[ \left( \frac {\Pi_{i} n_i} {n_i} \right)^{-1} \right]_{n_i} \right] _N $

I read somewhere that you can do this by induction... But I don't see how that would work...

  • $\begingroup$ The existence of a solution for the general case is an easy induction. The form is a little unpleasant to write out by induction. $\endgroup$ – André Nicolas Jan 10 '16 at 19:35
  • $\begingroup$ Mhm, I can imagine. Btw, is it possible to prove the solution for two congruences with induction? $\endgroup$ – user9750060 Jan 10 '16 at 19:39
  • $\begingroup$ Well, the usual proof of the Bezout "Identity" uses the least number principle, aka induction. Or else we prove the result using the Extended Euclidean Algorithm, whose correctness proof technically requires induction. $\endgroup$ – André Nicolas Jan 10 '16 at 19:44
  • $\begingroup$ It is easier to show that the solution is unique, so the solution is given by an injective map from a set with $m$ elements to a set with $m$ elements. Such a map must be bijective. $\endgroup$ – Peter Jan 10 '16 at 19:48
  • $\begingroup$ @AndréNicolas heh, I suppose 'easy induction' of this form is still too difficult for me, thanks anyway $\endgroup$ – user9750060 Jan 10 '16 at 19:53

I can give you a sequence of hints (for me the proof is more based on "Analysis/Synthesis" method)

Hint 1 : Prove that $\gcd(m_2m_3...m_n, \ m_1m_3...m_n, \ ..., \ m_1m_2...m_{n-1})=1$. You can use Euclid "generalized" lemma by contradiction.

Hint 2 : You can now use this to build a potential solution $x$ using Bachet-Bézout "generalized" theorem and multiplying by $x$ (don't forget to write $x$ in the fine way for one side of the equality). Then see what you obtain $\pmod{m_1...m_2}$.

Hint 3 : Try to determine a condition on Bachet-Bézout coefficients if $x$ satisfies the required property by thinking about invertible elements and Gauss "generalized" lemma.

Then it is the same thing as the trivial case for the uniqueness.

If this is not enough I will probably develop the hints or write the total answer (for the existence)


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.