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)\)
Solución:
(%i2) mcd ( a , b ) : = block ( [ r1 , r2 , r3 ] , r1 : a , r2 : b , r3 : mod ( r1 , r2 ) , while ( r3 > 0 ) do ( r1 : r2 , r2 : r3 , r3 : mod ( r1 , r2 ) ) , r2 ) $ mcd ( 21 , 15 ) ;
\[3\]
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}
Ejercicio: Crear un algoritmo que calcule el \(\mathbf{mcd}(43134,343)\) guardando los cocientes y los restos sucesivos.
Solución:
(%i2) algEucl ( a , b ) : = block ( [ q , r , i , n ] , q : [ floor ( a / b ) ] , r : [ mod ( a , b ) ] , i : 1 , n : b , while ( r [ i ] > 0 ) do ( q : append ( q , [ floor ( n / r [ i ] ) ] ) , r : append ( r , [ mod ( n , r [ i ] ) ] ) , n : r [ i ] , i : i + 1 ) , [ q , r ] ) $ algEucl ( 43134 , 343 ) ;
\[\left[ \left[ 125,1,3,12\right] ,\left[ 259,84,7,0\right] \right] \]
Procedimiento recursivo
Ejercicio: Crear un algoritmo recursivo que calcule el \(\mathbf{mcd}\).
Solución:
(%i2) mcd ( a , b ) : = if ( b = 0 ) then a else mcd ( b , mod ( a , b ) ) $ mcd ( 114 , 32 ) ;
\[\tag{%o2} 2\]
Ejercicio: Crear un algoritmo recursivo que calcule los cocientes en el cálculo de \(\mathbf{mcd}\).
Solución:
cEucl ( a , b ) : = if b = 0 then [ ] else cons ( floor ( a / b ) , cEucl ( b , mod ( a , b ) ) ) $ cEucl ( 43134 , 343 ) ;
\[\tag{%o2} \left[ 125{,}1{,}3{,}12\right] \]
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)\)?
Solución:
(%i1)
mcd ( a , b ) : = if ( b = 0 ) then a else mcd ( b , mod ( a , b ) ) $
(%i3)
mcm ( a , b ) : = abs ( a · b ) / mcd ( a , b ) $ mcm ( 30 , 25 ) ;
\[150\]
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)\]
Solución:
q : [ 125 , 1 , 3 , 12 ] $ r1 : a − q [ 1 ] · b $ r2 : b − q [ 2 ] · r1 $ 7 = r1 − q [ 3 ] · r2 $ rat ( % ) ;
\[\tag{%o5)/R} 7\mathop{=}\mathop{-}\left( 503 b\right) \mathop{+}4 a\]
Recordemos que \(a=43134\) y \(b=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||?
Solución:
mcd ( a , b ) : = if ( b = 0 ) then a else mcd ( b , mod ( a , b ) ) $ cEucl ( a , b ) : = if b = 0 then [ ] else cons ( floor ( a / b ) , cEucl ( b , mod ( a , b ) ) ) $
n : 54180 $ m : 47355 $ d : mcd ( n , m ) ; q : cEucl ( n , m ) ;
\[\tag{d} 105\]
\[\tag{q} \left[ 1\mathop{,}6\mathop{,}1\mathop{,}15\mathop{,}4\right] \]
r1 : a − q [ 1 ] · b $ r2 : b − q [ 2 ] · r1 $ r3 : r1 − q [ 3 ] · r2 $ d = r2 − q [ 4 ] · r3 $ rat ( % ) ;
\[\tag{%o11)/R} 105\mathop{=}127 b\mathop{-}111 a\]
v : [ − 111 , 127 ] $ [ 3 , 2 ] . v / sqrt ( v . v ) ; abs ( % ) , numer ;
\[\tag{%o13} \mathop{-}\left( \frac{79}{5 \sqrt{1138}}\right) \]
\[\tag{%o14} 0.4683666417157143\]
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||?
Solución:
cEucl ( a , b ) : = if b = 0 then [ ] else cons ( floor ( a / b ) , cEucl ( b , mod ( a , b ) ) ) $ q : cEucl ( 462 , 216 ) ;
\[\tag{q} \left[ 2\mathop{,}7\mathop{,}5\right] \]
m : ident ( 2 ) $ makelist ( m : m . matrix ( [ 0 , 1 ] , [ 1 , − q [ i ] ] ) , i , 1 , length ( q ) ) $ m : % [ length ( q ) ] ;
\[\tag{m} \begin{pmatrix}\mathop{-}7 & 36\\
v : [ m [ 1 , 1 ] , m [ 2 , 1 ] ] $ [ − 1 , 5 ] . v / sqrt ( v . v ) ; abs ( % ) , numer ;
\[\tag{%o7} \frac{82}{\sqrt{274}}\]
\[\tag{%o8} 4.953801165307452\]
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||?
Solución:
Por el ejercicio anterior sabemos que
(%i6) l : makelist (matrix ([0 ,1 ],[1 ,– q [1 ][i ]]),i ,1 ,length (q [1 ])); l2 : matrix ([1 ,0 ],[0 ,1 ])$ l3 : makelist (l2 : l2 .l [i ],i ,1 ,length (l )); print («Solución de Bezout: (« ,l3 [4 ][1 ,1 ],«,» ,l3 [4 ][2 ,1 ],«)» )$
(l) [ ( 0 1 1 − 125 ) , ( 0 1 1 − 1 ) , ( 0 1 1 − 3 ) , ( 0 1 1 − 12 ) ] (l3) [ ( 0 1 1 − 125 ) , ( 1 − 1 − 125 126 ) , ( − 1 4 126 − 503 ) , ( 4 − 49 − 503 6162 ) ] Solución de Bezout: ( 4 , − 503 )
(%i9) v : [l3 [4 ][1 ,1 ],l3 [4 ][2 ,1 ]]$ 4 ,– 3 ].v / sqrt (v .v ); abs (% ),numer ;
(%o8) 305 10121 (%o9) 3.03171328560307
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 ],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 ]]$
Ejemplo: Sea v=[a,b], la solución de Bezout de \(\mathbf{mcd}(5432,872)\). ¿Cuánto es, en valor absoluto, el producto escalar [3,-5].v/||v||?
Solución:
Calculemos los restos y los cocientes que utilizaremos posteriormente.
(%i9) n : 5432 $ m : 872 $ q : [ floor ( n / m ) ] $ r : [ mod ( n , m ) ] $ q : append ( q , [ floor ( m / r [ 1 ] ) ] ) $ r : append ( r , [ mod ( m , r [ 1 ] ) ] ) $ for i : 2 while r [ i ] > 0 do ( q : append ( q , [ floor ( r [ i − 1 ] / r [ i ] ) ] ) , r : append ( r , [ mod ( r [ i − 1 ] , r [ i ] ) ] ) ) $ q ; r ;
\[\left[ 6, 4, 2, 1, 3, 2\right] \]
\[\left[ 200, 72, 56, 16, 8, 0\right] \]
Declaremos la función que nos permita aplicar el algoritmo extendido de Euclides para encontrar la solución que buscamos.
(%i10) qm ( a ) : = matrix ( [ 0 , 1 ] , [ 1 , − a ] ) $
Apliquemos el algoritmo extendido de Euclides multiplicando las matrices generadas con los cocientes.
(%i12) M : ident ( 2 ) $ ml : makelist ( M : M . qm ( q [ i ] ) , i , 1 , length ( q ) ) ;
\[\left[ \begin{bmatrix}0 & 1\\1 & -6\end{bmatrix}, \begin{bmatrix}1 & -4\\-6 & 25\end{bmatrix}, \begin{bmatrix}-4 & 9\\25 & -56\end{bmatrix}, \begin{bmatrix}9 & -13\\-56 & 81\end{bmatrix}, \begin{bmatrix}-13 & 48\\81 & -299\end{bmatrix}, \begin{bmatrix}48 & -109\\-299 & 679\end{bmatrix}\right] \]
Tenemos la solución, la primera columna de la última matriz. Resolvamos el ejercicio.
(%i14) v : transpose ( col ( ml [ length ( q ) ] , 1 ) ) [ 1 ] $ [ 3 , − 5 ] . v / sqrt ( v . v ) , numer ;
\[5.412307287160986\]
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\}|.\]
Solución:
(%i1)
fi (n ): = block ([f ,i ],f : 1 ,i : 2 thru n – 1 do(mcd (i ,n )= 1 ) then f : f + 1 f $
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?
Solución:
(d) [ − 5 , 1 , 2 ]
(%i3) if(mod (46 ,d [3 ])= 0 ) then (print («Hay solución:» ),cprima : 46 / d [3 ],x : d [1 ]* cprima + 22 / d [3 ]* k ,y : d [2 ]* cprima – 4 / d [3 ]* k ,print («x=» ,x ),print («y=» ,y )$
Hay solución: x= 11 k − 115 y= 23 − 2 k
(%i4) sol (i ): = [ev (x ,k = i ),ev (y ,k = i )]$
(%i6)
id : floor (115 / 11 )$ makelist (sol (i ),i ,id ,id + 2 );
(%o6) [ [ − 5 , 3 ] , [ 6 , 1 ] , [ 17 , − 1 ] ]
(%o7) 13
Ejercicio: Sea \(v\) la menor de las soluciones positivas de 7x-11y=5, ¿cuál es el valor de [3,4].v?
Solución:
(%i6) a : 7 $ b : – 11 $ c : 5 $ d : eucl_ext (a ,b );
(d) [ − 3 , − 2 , 1 ]
(%i8) sol (k ): = [d [1 ]* (c / d [3 ])+ b / d [3 ]* k ,d [2 ]* (c / d [3 ])– a / d [3 ]* k ]$ sol (k );
(%o8) [ − 11 k − 15 , − 7 k − 10 ]
(%i11) solve (sol (k )[1 ],k ); p : floor (ev (k ,% )); makelist (sol (i ),i ,p – 2 ,p + 2 );
(%o9) [ k = − 15 11 ] (p) − 2 (%o11) [ [ 29 , 18 ] , [ 18 , 11 ] , [ 7 , 4 ] , [ − 4 , − 3 ] , [ − 15 , − 10 ] ]
(%o12) 37
Ejercicio: ¿Cuál es la suma de dígitos del \(\textbf{mcd}(1108955617, 2283735839)\)?
Solución:
Navegación de entradas