user
Suppose   

n

1
{\displaystyle {\displaystyle n\_{1}}}
,   

n

2
{\displaystyle {\displaystyle n\_{2}}}
,   

…
{\displaystyle {\displaystyle \ldots }}
,   

n

k
{\displaystyle {\displaystyle n\_{k}}}
   are positive integers that are pairwise co-prime.

Then, for any given sequence of integers   

a

1
{\displaystyle {\displaystyle a\_{1}}}
,   

a

2
{\displaystyle {\displaystyle a\_{2}}}
,   

…
{\displaystyle {\displaystyle \dots }}
,   

a

k
{\displaystyle {\displaystyle a\_{k}}}
,   there exists an integer   

x
{\displaystyle {\displaystyle x}}
   solving the following system of simultaneous congruences:

:   :   :   x


            ≡

            a

            1


            (
            mod


            n

            1
            )


            x


            ≡

            a

            2


            (
            mod


            n

            2
            )

             
             
            ⋮


            x


            ≡

            a

            k


            (
            mod


            n

            k
            )
            {\displaystyle {\displaystyle {\begin{aligned}x&\equiv a\_{1}{\pmod {n\_{1}}}\\x&\equiv a\_{2}{\pmod {n\_{2}}}\\&{}\ \ \vdots \\x&\equiv a\_{k}{\pmod {n\_{k}}}\end{aligned}}}}

Furthermore, all solutions   

x
{\displaystyle {\displaystyle x}}
   of this system are congruent modulo the product,   

N
=

n

1

n

2
…

n

k
{\displaystyle {\displaystyle N=n\_{1}n\_{2}\ldots n\_{k}}}
.

Task

Write a program to solve a system of linear congruences by applying the   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   

s
{\displaystyle {\displaystyle s}}
   where   

0
≤
s
≤

n

1

n

2
…

n

k
{\displaystyle {\displaystyle 0\leq s\leq n\_{1}n\_{2}\ldots n\_{k}}}
.

*Show the functionality of this program* by printing the result such that the   

n
{\displaystyle {\displaystyle n}}
's   are   

[
3
,
5
,
7
]
{\displaystyle {\displaystyle [3,5,7]}}
   and the   

a
{\displaystyle {\displaystyle a}}
's   are   

[
2
,
3
,
2
]
{\displaystyle {\displaystyle [2,3,2]}}
.

**Algorithm**:   The following algorithm only applies if the   

n

i
{\displaystyle {\displaystyle n\_{i}}}
's   are pairwise co-prime.

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

:   :   :   x
            ≡

            a

            i


            (
            mod


            n

            i
            )


            f
            o
            r

            i
            =
            1
            ,
            …
            ,
            k
            {\displaystyle {\displaystyle x\equiv a\_{i}{\pmod {n\_{i}}}\quad \mathrm {for} \;i=1,\ldots ,k}}

Again, to begin, the product   

N
=

n

1

n

2
…

n

k
{\displaystyle {\displaystyle N=n\_{1}n\_{2}\ldots n\_{k}}}
   is defined.

Then a solution   

x
{\displaystyle {\displaystyle x}}
   can be found as follows:

For each   

i
{\displaystyle {\displaystyle i}}
,   the integers   

n

i
{\displaystyle {\displaystyle n\_{i}}}
   and   

N

/

n

i
{\displaystyle {\displaystyle N/n\_{i}}}
   are co-prime.

Using the   Extended Euclidean algorithm,   we can find integers   

r

i
{\displaystyle {\displaystyle r\_{i}}}
   and   

s

i
{\displaystyle {\displaystyle s\_{i}}}
   such that   

r

i

n

i
+

s

i
N

/

n

i
=
1
{\displaystyle {\displaystyle r\_{i}n\_{i}+s\_{i}N/n\_{i}=1}}
.

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

:   :   :   x
            =

            ∑

            i
            =
            1

            k

            a

            i

            s

            i
            N

            /

            n

            i
            {\displaystyle {\displaystyle x=\sum \_{i=1}^{k}a\_{i}s\_{i}N/n\_{i}}}

and the minimal solution,

:   :   :   x


            (
            mod

            N
            )
            {\displaystyle {\displaystyle x{\pmod {N}}}}
            .
assistant
(formerly Perl 6)

**Translation of**: C

**Works with**: Rakudo version 2015.12

```
# returns x where (a * x) % b == 1
sub mul-inv($a is copy, $b is copy) {
    return 1 if $b == 1;
    my ($b0, @x) = $b, 0, 1;
    ($a, $b, @x) = (
	$b,
	$a % $b,
	@x[1] - ($a div $b)*@x[0],
	@x[0]
    ) while $a > 1;
    @x[1] += $b0 if @x[1] < 0;
    return @x[1];
}

sub chinese-remainder(*@n) {
    my \N = [*] @n;
    -> *@a {
	N R% [+] map {
	    my \p = N div @n[$_];
	    @a[$_] * mul-inv(p, @n[$_]) * p
	}, ^@n
    }
}

say chinese-remainder(3, 5, 7)(2, 3, 2);

```

Output:

```
23
```