Diario de clases

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:

---

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.

Solución:

---

Procedimiento recursivo

Ejercicio: Crear un algoritmo recursivo que calcule el \(\mathbf{mcd}\).

Solución:

---

Ejercicio: Crear un algoritmo recursivo que calcule los cocientes en el cálculo de \(\mathbf{mcd}\).

Solución:

---

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:

---

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:

---

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:

---

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:

---

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:

---

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

Solución:

---

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:

---

Ejercicio: Sea \(v\) la menor de las soluciones positivas de 7x-11y=5, ¿cuál es el valor de [3,4].v?

Solución:

---

 

Ejercicio: ¿Cuál es la suma de dígitos del \(\textbf{mcd}(1108955617, 2283735839)\)? 21 14 6

Solución:

Máximo común divisor Consideremos dos números enteros Si \(a\) y \(b\) distintos de cero, decimos que \(c\) es un divisor común de \(a\) y \(b\) si \(c|a\) y \(c|b\). Cuando existen, únicamente,…

1. El algoritmo de la división Dados dos números enteros \(a\) y \(b\), con \(a\) no nulo, la división euclídea asocia un cociente \(q\in\mathbb{Z}\) y un resto \(r\in\mathbb{Z}\), únicos, que verifican: \[b=q\,a+r,\quad…