Ejempo del Algoritmo Extendido de Euclides

Si tenemos una ecuación diofántica de primer grado tal que su expresión es de la forma a*x + b*y = MCD  (a,b) el Algoritmo Extendido nos permite calcular los valores de las incognitas x e y. A coantinuación se presenta dicho algoritmo en PseInt:

Proceso AlgoritmoExtendidoEuclides
Definir a como entero;
Definir b como entero;
Definir x como entero;
Definir y como entero;
Definir ux Como Entero;;
Definir uy como entero;
Definir cociente como entero;
Definir tmp como entero;
Definir tmpa como entero;
Definir tmpb como entero;
Definir continuar como Logico;
Definir expresion como cadena;

Escribir "De la expresion a*x + b*c = MCD (a,b)";
Escribir "Ingrese a:";
Leer a;

Escribir "Ingrese b:";
Leer b;

tmpa <-a;
tmpb <-b;

x <- 0;
ux <- 1;
y <- 1;
uy <- 0;

continuar <- verdadero;

Mientras continuar Hacer
cociente <- TRUNC (a/b);
tmp <- a;
a <- b;
b <- tmp % b;
tmp <- x;
x <- ux - cociente*x;
ux <- tmp;
tmp <- y;
y <- uy - cociente*y;
uy <- tmp;
Si b = 0 Entonces
continuar <- falso;
FinSi
FinMientras

Escribir ux,"x",tmpa,"+",uy,"x",tmpb,"=",a;


FinProceso

Basado en Wikipedia