######################## PROBLÈME 2: #########################

#@# 1)
InvMod := proc(x, N)
  local D,d,u;
  #@# on peut remplacer les deux lignes suivantes par
  #@# d := igcdex(x, N, 'u');
  D := Bezout(x,N);
  d := D[1]; u := D[2];
  if (d <> 1) then
    false;
  else
    u mod N;
  fi
end:
#@# bien sûr,  1/x mod N  marche directement!

#@# 2) résoud x = A mod a, x = B mod b [on suppose $ab <> 0$]
Chinois := proc(A,B, a, b)
  local D,d,u,v,m,x,M;
  D := Bezout(a,b);
  d := D[1]; u := D[2]; v := D[3];
  if (d <> 1 and A mod d <> B mod d) then
    false;
  else
    x := A + u*(a/d)*(B-A);
    M := a*b/d;
    [x mod M, M]
  fi;
end:
#@# noter que chrem ne sait pas traiter le cas $(a,b) > 1$

#@# 3) x = liste de résidus, m = liste de modules, de même longueurs
ChinoisN := proc(x, m)
  local i,d,X,M;
  X := x[1]; M := m[1];
  for i from 2 to nops(x) do
    d := Chinois(X,x[i], M,m[i]);
    if (d = false) then RETURN(false); fi;
    X := d[1]; M := d[2];  #@# X mod M solution des congruences 1..i
  od;
  [X, M];
end:
#@# une solution ``diviser pour régner'' serait plus efficace

#@# 4)
ChinoisN([3,2,5,5], [14,13,11,8]);