// algoritmo ricorsivo per il calcolo del mcd esteso
// al termine della funzione in v[0] v[1] sono memorizzati
// due numeri tali che   a v[0] + b v[1] = mcd(a,b) 
// Per semplicita' si suppone a>0 e b>=0
int gcdex(int a,int b,int v[])
{
  int q,r,d,miov[2];

  // caso base
  if(b==0) {
     v[0]=1; v[1]=0;    
     return a;
  }
  q = a/b;
  r = a%b;
  d = gcdex(b,r,miov);
  // vale: d=b miov[0] + r miov[1] = b miov[0] + (a-bq)miov[1]
  v[0] = miov[1];
  v[1] = miov[0] - q miov[1]
  return d;
}