# [Maxima] Chinese theorem

Minh Nguyen nguyenminh2 at gmail.com
Sun Nov 29 06:50:03 CST 2009

```Hi Konstantinos,

2009/11/29 Κωνσταντίνος Κωστας <kotzeve at hotmail.com>:
>
> Hello,again...Does anyone know if there is a function in maxima tha solves
> the chinese remainder theorem?

I'm not aware of such a function in the Maxima reference manual for
version 5.19.2. However, the following Maxima function implements the
Chinese remainder theorem:

{{{
crt(A, M) := block(
Mprod : product(M[i], i, 1, length(M)),
Mdiv : map(lambda([x], Mprod / x), M),
X : map(inv_mod, Mdiv, M),
x : sum(A[i]*X[i]*Mdiv[i], i, 1, length(M)),
return(mod(x, Mprod))
)\$
}}}

The list A contains integers you want to solve for, and M is a list of
moduli. Here are some examples on using the function crt():

{{{
(%o1)                               crt.mac
(%i2) A : [2, 3, 1]\$
(%i3) M : [3, 4, 5]\$
(%i4) x : crt(A, M);
(%o4)                                 11
(%i5) mod(x, 3);
(%o5)                                  2
(%i6) mod(x, 4);
(%o6)                                  3
(%i7) mod(x, 5);
(%o7)                                  1
(%i8) A : [4, 7, 3]\$
(%i9) M : [5, 8, 9]\$
(%i10) x : crt(A, M);
(%o10)                                39
(%i11) mod(x, 5);
(%o11)                                 4
(%i12) mod(x, 8);
(%o12)                                 7
(%i13) mod(x, 9);
(%o13)                                 3

--
Regards
Minh Van Nguyen

```