La Enciclopedia Libre Universal en Español dispone de una lista de distribución pública, enciclo@listas.us.es

Algoritmo extendido de Euclides

De la Enciclopedia Libre Universal en Español
Saltar a: navegación, buscar

Algoritmo extendido de Euclides.

int euclidesExtendido(int n, int a) {

int c,i; int g[],u[],v[];

g[0] = n; g[1] = a; u[0] = 1; u[1] = 0; v[0] = 0; v[1] = 1; i = 1; while (g[i] != 0) {

   c = g[i-1] / g[i];
   g[i+1] = g[i-1] % g[i];
   u[i+1] = u[i-1] - c * u[i];
   v[i+1] = v[i-1] - c * v[i];
   i++;

} while (v[i-1] < 0)

   v[i-1] = v[i-1] + n;

return(v[i-1]%n); }