Algoritmo de Euclides extendido

La ecuación diofántica lineal \(ax+by=c\) tiene solución si y solo si \(D\vert c,\) donde \(D= \text{mcd}(a,b).\) En ese caso, la ecuación queda simplificada dividiendo por \(D\) $$\frac{a}{D}x + \frac{b}{D}y = \frac{c}{D} \Leftrightarrow a’ x +b’y = c’, \tag{1}\label{eq1}$$ donde los coeficientes son primos entre sí, \(1 = \text{mcd}\left ( \frac{a}{D}, \frac{b}{D} \right )\). Este contenido...