[skip-to-content]

Sección 2.4 Algoritmo Extendido de Euclides

Definición 2.4.1.
(Combinación Lineal) Considere dos números enteros no nulos: \(a\) y \(b\text{.}\) Se denomina combinación lineal entera entre \(a\) y \(b\)a la expresión
\begin{equation*} x a + y b\text{,} \end{equation*}
con \(x,y \in \mathbb{Z}\text{.}\)

De la Identidad de Bézout (Teorema 2.4.2), se deriva el siguiente resultado (Corolario 2.4.3).

Es natural preguntarse (dado el Teorema 2.4.2 y el Corolario 2.4.3) si \(c=xa + yb\) implica \(c=(a,b)\text{.}\) ¡Esto es falso! Basta notar que \(6=4\cdot 3 + (-3)\cdot 2\text{;}\) pero \(6\neq 1\text{,}\) pues \((3,2)=1\text{.}\) Esto muestra que el reciproco de la Identidad de Bézout no es necesariamente cierto. Sin embargo, habrá una excepción.

Definición 2.4.5.
Se dice que dos números enteros \(a,b\) no nulos son coprimos o primos relativos si y sólo si \((a,b)=1\text{.}\)

A continuación, definiremos el Algoritmo Extendido de Euclides, técnica eficaz que permite calcular el máximo común divisor \(d\) entre dos números enteros no nulos. Adicionalmente, nos proporcionará enteros \(x,y\) tales que \(d=xa + y b\) (combinación lineal).

Encuentre números enteros \(x,y\) no nulos, tales que
\begin{equation*} 6=1248 x + 744 y. \end{equation*}

Sage nuevamente nos proporcionará una herramienta que permite calcular el máximo común divisor \(d\) entre dos números enteros \(a,b\) no nulos. Además, expresa \(d\) como combinación lineal entera entre \(a\) y \(b\text{.}\)