Problem Statement

Suppose

n

1

{\displaystyle n_{1}}

,

n

2

{\displaystyle n_{2}}

,

…

{\displaystyle \ldots }

,

n

k

{\displaystyle n_{k}}

are positive integers that are pairwise co-prime.   Then, for any given sequence of integers

a

1

{\displaystyle a_{1}}

,

a

2

{\displaystyle a_{2}}

,

…

{\displaystyle \dots }

,

a

k

{\displaystyle a_{k}}

,   there exists an integer

x

{\displaystyle x}

solving the following system of simultaneous congruences: Furthermore, all solutions

x

{\displaystyle x}

of this system are congruent modulo the product,

N

n

1

n

2

…

n

k

{\displaystyle N=n_{1}n_{2}\ldots n_{k}}

.

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 s}

where

0 ≤ s ≤

n

1

n

2

…

n

k

{\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 n}

's   are

[ 3 , 5 , 7 ]

{\displaystyle [3,5,7]}

and the

a

{\displaystyle a}

's   are

[ 2 , 3 , 2 ]

{\displaystyle [2,3,2]}

.

Algorithm:   The following algorithm only applies if the

n

i

{\displaystyle n_{i}}

's   are pairwise co-prime. Suppose, as above, that a solution is required for the system of congruences: Again, to begin, the product

N

n

1

n

2

…

n

k

{\displaystyle N=n_{1}n_{2}\ldots n_{k}}

is defined. Then a solution

x

{\displaystyle x}

can be found as follows: For each

i

{\displaystyle i}

,   the integers

n

i

{\displaystyle n_{i}}

and

N

/

n

i

{\displaystyle N/n_{i}}

are co-prime. Using the   Extended Euclidean algorithm,   we can find integers

r

i

{\displaystyle r_{i}}

and

s

i

{\displaystyle s_{i}}

such that

r

i

n

i

s

i

N

/

n

i

= 1

{\displaystyle r_{i}n_{i}+s_{i}N/n_{i}=1}

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

Let's start with the solution:

-module(crt).
-import(lists, [zip/2, unzip/1, foldl/3, sum/1]).
-export([egcd/2, mod/2, mod_inv/2, chinese_remainder/1]).

egcd(_, 0) -> {1, 0};
egcd(A, B) ->
    {S, T} = egcd(B, A rem B),
    {T, S - (A div B)*T}.

mod_inv(A, B) ->
    {X, Y} = egcd(A, B),
    if
        A*X + B*Y =:= 1 -> X;
        true -> undefined
    end.

mod(A, M) ->
    X = A rem M,
    if
        X < 0 -> X + M;
        true -> X
    end.

calc_inverses([], []) -> [];
calc_inverses([N | Ns], [M | Ms]) ->
    case mod_inv(N, M) of
        undefined -> undefined;
        Inv -> [Inv | calc_inverses(Ns, Ms)]
    end.

chinese_remainder(Congruences) ->
    {Residues, Modulii} = unzip(Congruences),
    ModPI = foldl(fun(A, B) -> A*B end, 1, Modulii),
    CRT_Modulii = [ModPI div M || M <- Modulii],
    case calc_inverses(CRT_Modulii, Modulii) of
        undefined -> undefined;
        Inverses ->
            Solution = sum([A*B || {A,B} <- zip(CRT_Modulii,
                                    [A*B || {A,B} <- zip(Residues, Inverses)])]),
            mod(Solution, ModPI)
    end.