Editing Chinese remainder theorem (section)

==Proof==
The existence and the uniqueness of the solution may be proven independently. However, the first proof of existence, given below, uses this uniqueness.

===Uniqueness===
Suppose that {{mvar|x}} and {{mvar|y}} are both solutions to all the congruences. As {{mvar|x}} and {{mvar|y}} give the same remainder, when divided by {{math|''n<sub>i</sub>''}}, their difference {{math|''x'' − ''y''}} is a multiple of each {{math|''n<sub>i</sub>''}}. As the {{math|''n<sub>i</sub>''}} are pairwise coprime, their product {{math|''N''}} also divides {{math|''x'' − ''y''}}, and thus {{mvar|x}} and {{mvar|y}} are congruent modulo {{math|''N''}}. If {{mvar|x}} and {{mvar|y}}  are supposed to be non-negative and less than {{math|''N''}} (as in the first statement of the theorem), then their difference may be a multiple of {{math|''N''}} only if {{math|1=''x'' = ''y''}}.

===Existence (first proof)===
The map
:<math>x \bmod N \mapsto (x \bmod n_1, \ldots, x\bmod n_k)</math>
maps [[congruence class]]es modulo {{math|''N''}} to sequences of congruence classes modulo {{math|''n<sub>i</sub>''}}. The proof of uniqueness shows that this map is [[injective]]. As the [[domain of a function|domain]] and the [[codomain]] of this map have the same number of elements, the map is also [[surjective]], which proves the existence of the solution.

This proof is very simple but does not provide any direct way for computing a solution. Moreover, it cannot be generalized to other situations where the following proof can.

===Existence (constructive proof)===
Existence may be established by an explicit construction of {{mvar|x}}.<ref>{{harvnb|Rosen|1993|page=136}}</ref> This construction may be split into two steps, first solving the problem in the case of two moduli, and then extending this solution to the general case by [[mathematical induction|induction]] on the number of moduli.

====Case of two moduli====
We want to solve the system:
:<math>
\begin{align}
  x &\equiv a_1 \pmod {n_1}\\
  x &\equiv a_2 \pmod {n_2},
\end{align}
</math>
where <math>n_1</math> and <math>n_2</math> are [[coprime]].

[[Bézout's identity]] asserts the existence of two integers <math>m_1</math> and <math>m_2</math> such that 
:<math>m_1n_1+m_2n_2=1.</math>
The integers <math>m_1</math> and <math>m_2</math> may be computed by the [[extended Euclidean algorithm]].

A solution is given by
:<math>x = a_1m_2n_2+a_2m_1n_1.</math>
Indeed, 
:<math>\begin{align}
x&=a_1m_2n_2+a_2m_1n_1\\
&=a_1(1 - m_1n_1) + a_2m_1n_1 \\
&=a_1 + (a_2 - a_1)m_1n_1,
\end{align}</math>
implying that <math>x \equiv a_1 \pmod {n_1}.</math> The second congruence is proved similarly, by exchanging the subscripts 1 and 2.

====General case====
Consider a sequence of congruence equations:
:<math>
\begin{align} 
  x &\equiv a_1 \pmod{n_1} \\ 
  &\vdots              \\ 
  x &\equiv a_k \pmod{n_k},
\end{align}
</math>
where the <math>n_i</math> are pairwise coprime. The two first equations have a solution <math>a_{1,2}</math> provided by the method of the previous section. The set of the solutions of these two first equations is the set of all solutions of the equation
:<math>x \equiv a_{1,2} \pmod{n_1n_2}.</math>

As the other <math>n_i</math> are coprime with <math>n_1n_2,</math> this reduces solving the initial problem of {{mvar|k}} equations to a similar problem with <math>k-1</math> equations. Iterating the process, one gets eventually the solutions of the initial problem.

===Existence (direct construction)===
For constructing a solution, it is not necessary to make an induction on the number of moduli. However, such a direct construction involves more computation with large numbers, which makes it less efficient and less used. Nevertheless, [[Lagrange interpolation]] is a special case of this construction, applied to [[polynomial]]s instead of integers.

Let <math>N_i = N/n_i</math> be the product of all moduli but one. As the <math>n_i</math> are pairwise coprime, <math>N_i</math> and <math>n_i</math> are coprime. Thus [[Bézout's identity]] applies, and there exist integers <math>M_i</math> and <math>m_i</math> such that
:<math>M_iN_i + m_in_i=1.</math>

A solution of the system of congruences is
:<math>x=\sum_{i=1}^k a_iM_iN_i.</math>
In fact, as <math>N_j</math> is a multiple of <math>n_i</math> for <math>i\neq j,</math>
we have
:<math>x \equiv a_iM_iN_i \equiv a_i(1-m_in_i) \equiv a_i \pmod{n_i}, </math>
for every <math>i.</math>