######################## PROBLÈME 1: #########################

#@# 1) solution itérative
pgcd := proc(A,B)
  local t,a,b;
  a := A; b := B; #@# Maple refuse de modifier les paramètres
  if (a = 0) then RETURN (b); fi;
  while (b <> 0) do
    t := b;
    b := a mod b;
    a := t;
  od;
  a;
end:

#@# solution récursive
pgcd2 := proc(a,b)
  if (b = 0) then  a;
  else             pgcd2(b, a mod b);
  fi;
end:

#@# 2)
Bezout := proc(a,b)
  local t,q,r,x,y,vx,vy;
  if (a = 0) then RETURN ([b,0,1]); fi;

  x := a; y := b; vx := 0; vy := 1;
  while (y <> 0) do
    q := iquo(x,y, 'r');
    t := vy;
    vy := vx - q*vy;
    vx := t;

    x := y;
    y := r;
  od;
  [x, (x-b*vx)/a, vx];
end:

#@# 3), 5)
with(linalg):

#@# renvoie l'indice de l'élément non nul de valeur absolue minimial
IndMin := proc(L)
  local i, k, m;
  k := 1; m := abs(L[k]);
  for i from 2 to nops(L) do
    if (L[i] <> 0 and abs(L[i]) < m) then
      k := i; m := abs(L[k]);
    fi
  od;
  k
end:

#@# A0 liste, renvoie B = (delta,0...0) et U tq A U = B
BezoutN := proc(A0)
  local n, U, A, i, k, m, q, r;
  A := A0; n := nops(A);
  U := array(identity, 1..n,1..n);
  k := IndMin(A); m := abs(A[k]);
  while true do
    print(A, k); #@# pour le voir fonctionner...
    if (k > 1) then
      i := A[1]; A[1] := A[k]; A[k] := i;
      U := swapcol(U, 1, k);
    fi;
    for i from 2 to n do
      q := iquo(A[i], m, 'A[i]');
      U := addcol(U, 1, i, -q);
    od;
    k := IndMin(A); m := abs(A[k]);
    if (k = 1) then RETURN ([A,U]); fi
  od;
end:

#@# Exemple:
A0 := [116085838, 181081878, 314252913, 10346840]:
#@# 
#@# comparer BezoutN(A0) avec ihermite(matrix(4,1,A0), 'U')
#@# La plus petite solution (norme $L_2$) est $[-88,352,-167,-101]$

A1 := [763836, 1066557, 113192, 1785102, 1470060, 3077752,
       114793, 3126753, 1997137, 2603018]:
#@# La plus petite solution est $[3,-1,1,2,-1,-2,-2,-2,2,2]$