El pasado día vimos que el algoritmo de Euclides se fundamenta en el teorema:
Teorema: Si \(a\) y \(b\) son números enteros, \[\mathbf{mcd}(a,b)=\mathbf{mcd}(b,r),\] donde \(r\) es el resto del algoritmo de la división para \(a\) y \(b\) (\(a=qb+r\)).
Algoritmo para el cálculo del mcd
\[\begin{array}{l} r=[b,\mathbf{mod}(b,a)];\\ i=2;\\ \mathbf{while}(r[i]>0) \\ \qquad r[i++]=\mathbf{mod}(r[i-1],r[i]); \\ \mathbf{end}\\ \mathbf{print}(«\mathbf{mcd}:», r[i-1])\end{array} \]
Este algoritmo nos calcula el mcd; sin embargo, para posteriores ejercicios utilizaremos el proceso pasado que vimos. Por ejemplo, para calcular el \(\mathbf{mcd}(43134,343)\) construimos la siguiente tabla:
cociente |
125 |
1 |
3 |
12 |
43134 |
343 |
259 |
84 |
7 |
259 |
84 |
7 |
0 |
resto |
Tanto la fila cociente como la fila resto las utilizaremos más adelante. Veamos cómo obtenemos ambas filas con un algoritmo:
Algoritmo de Euclides
\[\begin{array}{l}
q=\lfloor b/a\rfloor;\\
r=\mathbf{mod}(b,a);\\
i=1;\\
n=a;\\
\mathbf{while}(r[i]>0) \\
\qquad q[i++]=\lfloor n/r[i]\rfloor ;\\
\qquad r[i++]=\mathbf{mod}(n,r[i]); \\
\qquad n=r[i];\\
\qquad i=i+1;\\
\mathbf{end}\\
\mathbf{print}(«Cocientes:», q)\\
\mathbf{print}(«Restos:», r)\end{array} \]
mcm
Ya estamos en condiciones para determinar el \(\mathbf{mcm}\) utilizando:
Teorema: Dados dos números enteros \(a\) y \(b\), entonces \[\mathbf{mcm}(a,b)=\frac{|ab|}{\mathbf{mcd}(a,b)}\]
Teorema de Bézout
Teorema(Bézout):
Si \(a\) y \(b\) son números enteros, entonces existen enteros \(x\) e \(y\) tales que \[ax + by =mcd(a,b)\]
Sin embargo, la solución de la ecuación anterior no es única. El siguiente resultado nos proporciona todas las soluciones:
Teorema(Bezout): Si \(x_0,y_0\in\mathbb{Z}\) son tales que \(nx_0+my_0=\mathbf{mcd}(n,m)\), se cumple que\[n\left(x_0-\frac{m}{\mathbf{mcd}(n,m)}k\right)+m\left(y_0+\frac{n}{\mathbf{mcd}(n,m)}k\right)=\mathbf{mcd}(n,m)\, \forall k\in\mathbb{Z}\]
Por comodidad, a todas las posibles soluciones \((x,y)\in\mathbb{Z}^2\), tales que \(nx+my=\mathbf{mcd}(n,m)\), les llamaremos soluciones de Bezout de \(\mathbf{mcd}(n,m)\).
El calculo de una de las soluciones anteriores será un problema recurrente, aquí propondremos dos procedimientos para obtenerla, ambas se basan el los números obtenidos en el desarrollo del algoritmo de Euclides:
Con un proceso recursivo
Ejemplo: Sea v=[a,b], la solución de Bezout de \(\mathbf{mcd}(54180,47355)\). ¿Cuánto es, en valor absoluto, el producto escalar [3,2].v/||v||?
Con matrices
Ejemplo: Sea v=[a,b], la solución de Bezout de \(\mathbf{mcd}(43134,343)\). ¿Cuánto es, en valor absoluto, el producto escalar [4,-3].v/||v||?
Ejercicio: Sean \(F_a\) y \(F_b\) dos números de Fermat compuestos, tales que \(F_a<F_b\), ¿cuál es el \(\mathbf{mcd}(F_a,F_b)\)? |