Algoritmo euclídeo extendido

Carta Común · N.º 254540

En aritmética y programación, el algoritmo euclídeo extendido es una generalización del algoritmo de Euclides, que además del máximo común divisor (mcd) de los enteros a y b, también calcula los coeficientes de la identidad de Bézout, que son los enteros x e y tales que a x + b y = mcd ⁡ ( a , b ) {\displaystyle ax+by=\operatorname {mcd} (a,b)} ; generalmente se denota como xmcd ⁡ ( a , b ) {\displaystyle \operatorname {xmcd} (a,b)} . Este es un algoritmo de certificación, porque el mcd es el único número que puede satisfacer simultáneamente esta ecuación y dividir los dos datos de entrada.​ Permite calcular también, casi sin coste de computación adicional, los cocientes de a y b por su máximo común divisor. El algoritmo euclídeo extendido también hace referencia…

Leer en Wikipedia