Suppose &nbsp; <math>n_1</math>, &nbsp; <math>n_2</math>, &nbsp; <math>\ldots</math>, &nbsp; <math>n_k</math> &nbsp; are positive [[integer]]s that are pairwise co-prime. &nbsp;

Then, for any given sequence of integers &nbsp; <math>a_1</math>, &nbsp; <math>a_2</math>, &nbsp; <math>\dots</math>, &nbsp; <math>a_k</math>, &nbsp; there exists an integer &nbsp; <math>x</math> &nbsp; solving the following system of simultaneous congruences:

::: <math>\begin{align}
  x &\equiv a_1 \pmod{n_1} \\
  x &\equiv a_2 \pmod{n_2} \\
    &{}\  \  \vdots \\
  x &\equiv a_k \pmod{n_k}
\end{align}</math>

Furthermore, all solutions &nbsp; <math>x</math> &nbsp; of this system are congruent modulo the product, &nbsp;  <math>N=n_1n_2\ldots n_k</math>.


;Task:
Write a program to solve a system of linear congruences by applying the &nbsp; [[wp:Chinese Remainder Theorem|Chinese Remainder Theorem]].

If the system of equations cannot be solved, your program must somehow indicate this.

(It may throw an exception or return a special false value.)

Since there are infinitely many solutions, the program should return the unique solution &nbsp; <math>s</math> &nbsp; where &nbsp; <math>0 \leq s \leq n_1n_2\ldots n_k</math>.


''Show the functionality of this program'' by printing the result such that the &nbsp; <math>n</math>'s &nbsp; are &nbsp; <math>[3,5,7]</math> &nbsp; and the &nbsp; <math>a</math>'s &nbsp; are &nbsp; <math>[2,3,2]</math>.


'''Algorithm''': &nbsp; The following algorithm only applies if the &nbsp; <math>n_i</math>'s &nbsp; are pairwise co-prime.

Suppose, as above, that a solution is required for the system of congruences:

::: <math>x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \ldots, k</math>

Again, to begin, the product &nbsp; <math>N = n_1n_2 \ldots n_k</math> &nbsp; is defined.

Then a solution &nbsp; <math>x</math> &nbsp; can be found as follows:

For each &nbsp; <math>i</math>, &nbsp; the integers &nbsp; <math>n_i</math> &nbsp; and &nbsp; <math>N/n_i</math> &nbsp; are co-prime.

Using the &nbsp; [[wp:Extended Euclidean algorithm|Extended Euclidean algorithm]], &nbsp; we can find integers &nbsp; <math>r_i</math> &nbsp; and &nbsp; <math>s_i</math> &nbsp; such that &nbsp; <math>r_i n_i + s_i N/n_i = 1</math>.

Then, one solution to the system of simultaneous congruences is:

::: <math>x = \sum_{i=1}^k a_i s_i N/n_i</math>

and the minimal solution,

::: <math>x \pmod{N}</math>.
<br><br>