49 lines
2.4 KiB
Text
49 lines
2.4 KiB
Text
Suppose <math>n_1</math>, <math>n_2</math>, <math>\ldots</math>, <math>n_k</math> are positive [[integer]]s that are pairwise co-prime.
|
|
|
|
Then, for any given sequence of integers <math>a_1</math>, <math>a_2</math>, <math>\dots</math>, <math>a_k</math>, there exists an integer <math>x</math> 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 <math>x</math> of this system are congruent modulo the product, <math>N=n_1n_2\ldots n_k</math>.
|
|
|
|
|
|
;Task:
|
|
Write a program to solve a system of linear congruences by applying the [[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 <math>s</math> where <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 <math>n</math>'s are <math>[3,5,7]</math> and the <math>a</math>'s are <math>[2,3,2]</math>.
|
|
|
|
|
|
'''Algorithm''': The following algorithm only applies if the <math>n_i</math>'s 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 <math>N = n_1n_2 \ldots n_k</math> is defined.
|
|
|
|
Then a solution <math>x</math> can be found as follows:
|
|
|
|
For each <math>i</math>, the integers <math>n_i</math> and <math>N/n_i</math> are co-prime.
|
|
|
|
Using the [[wp:Extended Euclidean algorithm|Extended Euclidean algorithm]], we can find integers <math>r_i</math> and <math>s_i</math> such that <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>
|