Algoritmo Extendido de Euclides

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{.}\)

Teorema 2.4.2.

(Identidad de Bézout) Sean \(a,b \in \mathbb{Z}\) no nulos. Si \(d=(a,b)\text{,}\) entonces existen enteros \(x,y\) (no necesariamente únicos) tales que

\begin{equation*} d=x a + y b\text{.} \end{equation*}

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

Corolario 2.4.3.

Sean \(a,b \in \mathbb{Z}\) no nulos. Si \(d=(a,b)\text{,}\) entonces \(d\) es el menor entero positivo tal que está en combinación lineal entera entre \(a\) y \(b\text{.}\)

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.

Proposición 2.4.4.

Sean \(a,b \in \mathbb{Z}\) no nulos. Si \((a,b)=1\text{,}\) entonces existen enteros \(x,y\) (no necesariamente únicos) si y sólo si

\begin{equation*} 1=xa + yb\text{.} \end{equation*}

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{.}\)

Proposición 2.4.6.

Sean \(a,b,c\in \mathbb{Z}\) con \(a,b\neq 0 \text{.}\) Si \(a|bc\) y \((a,b)=1\text{,}\) entonces \(a|c\text{.}\)

Proposición 2.4.7.

Sean \(a,b,c\in \mathbb{Z}\) con \(a,b,c\neq 0\text{.}\) Entonces

\begin{equation*} (a,b,c)=((a,b),c)\text{.} \end{equation*}

Proposición 2.4.8.

Sean \(a,b,q,r\in \mathbb{Z}\) con \(a,b,q,r\neq 0\text{.}\) Si \(a=qb+r\text{,}\) entonces

\begin{equation*} (a,b)=(b,r). \end{equation*}

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).

Algoritmo 2.4.9.

(Algoritmo Extendido de Euclides)

Ejercicio 2.4.10.

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{.}\)