7.3: Algoritmo euclidiano

¿Cómo encontramos\(\operatorname{gcd}(a, b)\), para\(a, b \in \mathbb{N}\)? Uno podría invocar el Teorema Fundamental de la Aritmética y comparar las descomposiciones principales de\(a\) y\(b\). Supongamos\[a=\prod_{n=1}^{N} p_{n}^{r_{n}}\] y\[b=\prod_{n=1}^{N} p_{n}^{s_{n}}\] donde\(r_{n}, s_{n} \in \mathbb{N}\) para\(1 \leq n \leq N\). Si es\(t_{n}=\min \left(r_{n}, s_{n}\right)\) por\(1 \leq n \leq N\), entonces\[\operatorname{gcd}(a, b)=\prod_{n=1}^{N} p_{n}^{t_{n}}\] Sin embargo, encontrar la descomposición prima de un entero puede ser bastante difícil. Definiremos una operación sobre pares de enteros que después de un número razonable de aplicaciones producirá el mayor divisor común de los enteros.

Si\(a, b \in \mathbb{N}, a>b>0\), defina\(E: \mathbb{N}^{2} \rightarrow \mathbb{N}^{2}\) por\[E(a, b)=(b, r)\] dónde\(r\) está el resto único (al dividir\(a\) por\(b\)) cuya existencia fue probada en el Algoritmo de División. Es decir, si\[a=q b+r\] con\(0 \leq r<b\), entonces defina\[E(a, b):=(b, r) .\] Si\(b=0\), entonces\[E(a, 0)=(a, 0) .\] vamos Let\((a, b) \in \mathbb{N}^{2}, a>b>0\). Definimos una secuencia de elementos en\(\mathbb{N}^{2}\),\(\left\langle E_{i}(a, b) \mid i \in \mathbb{N}\right\rangle\), por recursión:\[E_{0}(a, b)=(a, b)\] y si Mientras\(n>0\)\[E_{n}(a, b)=E\left(E_{n-1}(a, b)\right) .\]\(E_{n}(a, b)\) tenga componentes distintos de cero, la secuencia de segundos componentes es estrictamente decreciente, por lo que es claro que la secuencia debe eventualmente fijarse en un par ordenado (ver Ejercicio 4.11). Por el Algoritmo de División, esto ocurrirá cuando el segundo componente sea igual a 0. Dejar\(k\) ser el entero más pequeño tal que\[E_{k}(a, b)=E_{k+1}(a, b) .\] Entonces decimos que se\(\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\) estabiliza al paso\(k\). Para\(n \geq k\),\[E_{n}(a, b)=E_{n+1}(a, b)=E_{k}(a, b) .\] Si\(\left\langle E_{n}(a, b)\right\rangle\) se estabiliza al paso\(k\), es obvio que\(k \leq b\). Por lo general, la secuencia se estabiliza mucho más rápido que esto. TEOREMA 7.12. Vamos\(a, b \in \mathbb{N}, a>b>0\). El componente distinto de cero sobre el que se\[\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\] estabiliza la secuencia es\(\operatorname{gcd}(a, b)\).

Comprobante. \(a\)Déjese fijar, argumentamos por inducción sobre el menor de los enteros,\(b\).

Caso base:\(b=1\)

Luego para cualquiera\(a>1\),\[E(a, 1)=(1,0)\] y la secuencia se\(\left\langle E_{n}(a, 1)\right\rangle\) estabiliza en el paso 1 con componente distinto de cero\(1 .\)

Paso de inducción:

Vamos\(b>1\). Supongamos que el resultado se mantiene para todos\(c<b\), es decir, para cualquier\((a, c) \in \mathbb{R}^{2}\)\(c<b<a\), donde, es el componente distinto de cero del par ordenado en el que se\(\left\langle E_{n}(a, c)\right\rangle\) estabiliza la secuencia\(\operatorname{gcd}(a, c)\). Mostramos que el componente distinto de cero del par ordenado en el que se\(\left\langle E_{n}(a, b)\right\rangle\) estabiliza la secuencia es\(\operatorname{gcd}(a, b)\). Si\(a>b>0\) entonces\[E(a, b)=(b, a-q b)\] donde\(0 \leq a-q b<b\). Por la hipótesis de inducción, el componente distinto de cero del par ordenado en el que se\(\left\langle E_{n}(b, a-q b)\right|\)\(n \in \mathbb{N}\rangle\) estabiliza la secuencia es\(\operatorname{gcd}(b, a-q b)\). Por Proposición\(7.9\)\[\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a-q b) .\] Entonces el componente distinto de cero del par ordenado en el que se\[\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\] estabiliza la secuencia es\(\operatorname{gcd}(a, b)\). Por el principio de inducción, el resultado se mantiene para todos los pares ordenados\((a, b) \in \mathbb{N}^{2}\) donde\(a>b>0\).

Un algoritmo es un conjunto de instrucciones computacionales ejecutables. El algoritmo euclidiano es el siguiente conjunto de instrucciones:

Dado un par de números naturales,\(a>b>0\), computar la secuencia\(\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\) hasta que la secuencia se estabilice. El componente distinto de cero del par ordenado sobre el que se estabiliza la secuencia es\(\operatorname{gcd}(a, b)\).

EJEMPLO 7.13. Dejar\(a=29712375\) y\(b=119119\). Encuentra el\(\operatorname{gcd}(a, b)\). Utilizamos el Algoritmo Euclidiana. Entonces,\[\begin{gathered} E_{0}(a, b)=(a, b) \\ E_{1}(a, b)=E(a, b)=(b, 51744) \\ E_{2}(a, b)=E(b, 51744)=(51744,4851) \\ E_{3}(a, b)=E(51744,4851)=(4851,1078) \\ E_{4}(a, b)=E(4851,1078)=(1078,539) \\ E_{5}(a, b)=E(1078,539)=(539,0) . \end{gathered}\] por lo tanto\(\operatorname{gcd}(a, b)=539\). Si empleas el Teorema Fundamental de la Aritmética, con algún trabajo puedes determinar\[119,119=\left(7^{2}\right)(11)(13)(17) .\] eso\[29,712,375=\left(3^{2}\right)\left(5^{3}\right)\left(7^{4}\right)(11)\] y So\(\operatorname{gcd}(a, b)=\left(7^{2}\right)(11)=539\).