Diario de clases

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, como divisores comunes 1 y -1 de los números \(a\) y \(b\), estos se llaman coprimos o números primos entre sí.

Un número entero \(d\) se llama máximo común divisor de los números \(a\) y \(b\), \(d=\textbf{mcd}(a,b)\), cuando:

1. d es divisor común de los números \(a\) y \(b\) y
2. \(c\) es divisor de \(a\) y \(b\), entonces \(c|d\).

Algoritmo de Euclides

El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (mcd). Se basa en el siguiente resultado:

Teorema:
Si \(a\) y \(b\) son números enteros, \[\textbf{mcd}(a,b)=\textbf{mcd}(b,r),\] donde \(r\) es el resto del algoritmo de la división para \(a\) y \(b\) (\(a=qb+r\)).

Utilizando este resultado calculamos el mcd(a,b) de dos enteros (ambos >0, suponemos a > b) definiendo q_i y r_i recursivamente mediante las ecuaciones:

a = bq₁ + r₁ (0<r₁<b)

b = r₁q₂ + r₂ (0<r₂<r₁)

r₁ = r₂q₃ + r₃ (0<r₃<r₂)

….

r_k-3 = r_k-2q_k-1 + r_k-1 (0<r_k-1<r_k-2)

r_k-2 = r_k-1q_k (r_k=0)

Del teorema anterior, se sigue que:

\[\textbf{mcd}(a,b)=\textbf{mcd}(b,r_1)=\textbf{mcd}(r_1,r_2)=\ldots=\textbf{mcd}(r_{k-2},r_{k-1})=r_{k-1}\]

En general, es que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

Ejemplo: Calcular \(\textbf{mcd}(866775, 138705)\)

Solución:

Ejemplo: Calcular \(\textbf{mcd}(125846,56985214)\)

Solución:

MCD con la calculadora

Teorema de Bézout

Teorema: Si \(d=mcd(a,b)\), entonces
\[\exists x,y\in\mathbb{Z};\, ax+by=d.\]

Teorema de Euclides: Para todo \(a,b,c\in\mathbb{Z}\) si \(a|(bc)\) y \(mcd(a,b)=1\), entonces \(a|c\)

Solución:

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||?

Solución:

Ejemplo: Calcular los cocientes y restos necesarios para resolver \[43134x+343y=\mathbf{mcd}(43134,343)\]

Solución:

Con matrices

Ejemplo: Resolvamos utilizando matrices \[43134x+343y=\mathbf{mcd}(43134,343)\]

Solución:

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:

Mínimo común múltiplo

Aunque no lo utilizaremos tanto como el mcd también podemos definir el menor múltiplo común de a un conjunto de enteros:
Un número entero \(m\) se llama mínimo común múltiplo de los números \(a\) y \(b\), que notaremos por \(m=mcm(a,b)\), cuando:

1. \(a|m\) y \(b|m\); es decir,m es un múltiplo común de los números \(a\) y \(b\) y
2. \(c\in\mathbb{Z}^+\) es un múltiplo de \(a\) y \(b\), entonces \(m\leq c\).

Teorema: Dados dos números enteros \(a\) y \(b\), entonces \[mcm(a,b)=\frac{|ab|}{\mathbf{mcd}(a,b)}\]

Mínimo común múltiplo con la calculadora

Ecuación diofántica de 2 variables

Al tratar el Teorema de Bézout vemos que podemos resolver la ecuación $ax+by=\mathbf{mcd(a,b)}$ con soluciones $(x,y)\in\mathbb{Z}^2$. Vemamos como generalizamos este resultado.

Definición: LLamaremos ecuación diofántica de dos variables a la ecuación \[ax+by=c,\] siendo $a,b,c\in\mathbb{Z}$ con soluciones $(x,y)\in\mathbb{Z}^2$.

Teorema: La ecuación diofántica \[ax+by=c,\] tiene solución si, y solo si, $\mathbf{mcd}(a,b)|c$.

Si una ecuación diofántica tiene solución, nos apoyamos en el hecho de la existencia de una solución particular, \[ax_0+by_0=\mathbf{mcd}(a,b),\] dada por el Teorema de Bezout, y esto nos permitirá encontrar las infinitas soluciones.

Teorema: La ecuación \(ax+by=c\), donde \(d=\mathbf{mcd}(a,b)\) divide a \(c\), tendrá por solución general:
\[\begin{array}{l} X=x_0\frac{c}{d}+\frac{b}{d}k\\ Y=y_0\frac{c}{d}-\frac{a}{d}k \end{array},\]

donde \((x_0,y_0)\) es una solución de la ecuación \(ax+by=\mathbf{mcd}(a,b)\).

Ejercicio: Resolver la ecuación diofántica \(4x+22y=46\).

Solución:

Ejercicio: Resolver la ecuación diofántica \(6x+15y=36\).

Solución:

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

Solución:

Veamos otra forma de afrontar cuando uno de los coeficientes \(a\) o \(b\), de la ecuación \(ax+by=c\) es negativo:

Ejercicio: Sea v\(:(x_m,y_m)\) la solución de 48x-27y=129, tal que \(y_m=\mathbf{max}\{y_s<0;\ 48x_s-27y_s=129\}\). ¿Cuál es el valor de [1,-2].v?

Solución:

Solución:

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…