Chinese remainder theorem: Difference between revisions

/* Function that checks pairwise coprimality */

check_pwc(lst):=block(

sublist(cartesian_product_list(makelist(i,i,length(lst)),makelist(i,i,length(lst))),lambda([x],x[1]#x[2])),

makelist([lst[%%[i][1]],lst[%%[i][2]]],i,length(%%)),

makelist(apply('gcd,%%[i]),i,length(%%)),

if length(unique(%%))>1 then false)$

/* Chinese remainder function */

c_remainder(A,N):=if check_pwc(N)=false then "chinese remainder theorem not applicable" else block(

cn:apply("*",N),

makelist(gcdex(cn/N[i],N[i]),i,1,length(N)),

makelist(A[i]*%%[i][1]*cn/N[i],i,1,length(N)),

apply("+",%%),

mod(%%,cn));