Editing Euclidean algorithm (section)

=== Chinese remainder theorem ===
Euclid's algorithm can also be used to solve multiple linear Diophantine equations.<ref>{{Harvnb|Rosen|2000|pp=143–170}}</ref> Such equations arise in the [[Chinese remainder theorem]], which describes a novel method to represent an integer ''x''. Instead of representing an integer by its digits, it may be represented by its remainders ''x''<sub>''i''</sub> modulo a set of ''N'' coprime numbers ''m''<sub>''i''</sub>:<ref>{{Harvnb|Schroeder|2005|pp=194–195}}</ref>
: <math>
\begin{align}
x_1 & \equiv x \pmod {m_1} \\
x_2 & \equiv x \pmod {m_2} \\
& \,\,\,\vdots \\
x_N & \equiv x \pmod {m_N} \,.
\end{align}
</math>

The goal is to determine ''x'' from its ''N'' remainders ''x''<sub>''i''</sub>. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus ''M'' that is the product of all the individual moduli ''m''<sub>''i''</sub>, and define ''M''<sub>''i''</sub> as
: <math> M_i = \frac M {m_i}. </math>

Thus, each ''M''<sub>''i''</sub> is the product of all the moduli ''except'' ''m''<sub>''i''</sub>. The solution depends on finding ''N'' new numbers ''h''<sub>''i''</sub> such that
: <math> M_i h_i \equiv 1 \pmod {m_i} \,. </math>

With these numbers ''h''<sub>''i''</sub>, any integer ''x'' can be reconstructed from its remainders ''x''<sub>''i''</sub> by the equation
: <math> x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \pmod M \,.</math>

Since these numbers ''h''<sub>''i''</sub> are the multiplicative inverses of the ''M''<sub>''i''</sub>, they may be found using Euclid's algorithm as described in the previous subsection.