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 \(\mathbf{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} \]
Ejercicio: Crear una algoritmo que calcule el \(\mathbf{mcd}(a,b)\)
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} \]
Ejercicio: Crear un algoritmo que calcule el \(\mathbf{mcd}(43134,343)\) guardando los cocientes y los restos sucesivos.
Procedimiento recursivo
Ejercicio: Crear un algoritmo recursivo que calcule el \(\mathbf{mcd}\).
Ejercicio: Crear un algoritmo recursivo que calcule los cocientes en el cálculo de \(\mathbf{mcd}\).
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)}\]
Ejemplo: ¿Cuál es el valor de \(\mathbf{mcm}(30,25)\)?
Teorema de Bézout
Con un proceso recursivo
Ejemplo: Utilizar los cocientes y restos obtenidos del ejercicio anterior para resolver \[43134x+343y=\mathbf{mcd}(43134,343)\]
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}(462,216)\). ¿Cuánto es, en valor absoluto, el producto escalar [-1,5].v/||v||?
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||?
Algoritmo extendido de Euclides
El proceso que hemos calculado con matrices lo podemos programar de la siguiente forma:
| (%i1) | eucl_ext(a,b):=block([s,t,r], s:[1,0,0], t:[0,1,0], r:[a,b], while (r[2]>0) do ( s[3]:s[1]–floor(r[1]/r[2])*s[2], t[3]:t[1]–floor(r[1]/r[2])*t[2], s:[s[2],s[3],0], t:[t[2],t[3],0], r:[r[2],mod(r[1],r[2])] ), [s[1],t[1],r[1]] )$ |
Función \(\varphi\) de Euler
Ejercicio: Para \(n\in\mathbb{Z}^+\), se define la función \(\varphi\) de Euler como \[\varphi (n)=|\{m\in\mathbb{Z}^+|m<n, mcd(n,m)=1\}|.\]
Crear una función en maxima que determine \(\varphi(n)\) para \(n\in\mathbb{Z}^+\).
Ecuaciones diofánticas de dos variables
Ejercicio: Sea \(v\) la menor de las soluciones positivas de 4x+22y=46, ¿cuál es el valor de [3,-5].v?
Ejercicio: Sea \(v\) la menor de las soluciones positivas de 7x-11y=5, ¿cuál es el valor de [3,4].v?
| Ejercicio: ¿Cuál es la suma de dígitos del \(\textbf{mcd}(1108955617, 2283735839)\)? |