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:
d es divisor común de los números \(a\) y \(b\) y
\(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 qi y ri recursivamente mediante las ecuaciones:
\[\begin{align*}
866775&=(6)138705+34545\\
138705&=(4)34545+525\\
34545&=(4)525+420\\
525&=(1)420+105\\
420&=(4)105+0
\end{align*}\]
Consecuentemente, el máximo común divisor es 105.
\[\begin{align*}
56985214&=(452)125846+102822\\
125846&=(1)102822+23024\\
102822&=(4)23024+10726\\
23024&=(2)10726+1572\\
10726&=(6)1572+1294\\
1572&=(1)1294+278\\
1294&=(4)278+182\\
278&=(1)182+96\\
182&=(1)96+86\\
96&=(1)86+10\\
86&=(8)10+6\\
10&=(1)6+4\\
6&=(1)4+2\\
4&=(2)2+0
\end{align*}\]
Consecuentemente, el máximo común divisor es 2.
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\)
Si \(a|(bc)\), entonces \(\exists n\in\mathbb{Z}\) tal que \(bc=an\). Además, si \(mcd(a,b)=1\), el resultado anterior nos dice que \(\exists x,y\in\mathbb{Z};\, ax+by=1\). Si multiplicamos la última igualdad por \(c\) tendremos:
\[
\begin{align*}
c&=axc+byc \\
&=axc+(bc)y \\
&=axc+(an)y \\
&=a(xc+ny) \\
\end{align*}
\]
Consecuentemente, \(a|c\).
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||?
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||?
Determinemos los cocientes
cociente
2
7
5
462
216
30
6
30
6
0
resto
Ahora consideramos las matrices \[\begin{bmatrix}0 & 1\\
1 & -2\end{bmatrix}{,}\begin{bmatrix}0 & 1\\
1 & -7\end{bmatrix}{,}\begin{bmatrix}0 & 1\\
1 & -5\end{bmatrix},\]
y hacemos la multiplicación
\[\begin{bmatrix}0 & 1\\
1 & -2\end{bmatrix}.\begin{bmatrix}0 & 1\\
1 & -7\end{bmatrix}.\begin{bmatrix}0 & 1\\
1 & -5\end{bmatrix}=\begin{bmatrix}-7 & 36\\
15 & -77\end{bmatrix}.\]
El vector que buscamos el la primera columna del producto de matrices \(v:[-7,15]\). Podemos verificar que \[-7\cdot 462+15\cdot 216=6\]
Ahora solo nos resta calcular: \[[-1,5].v/\|v\|\approx 4.95\]
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:
\(a|m\) y \(b|m\); es decir,m es un múltiplo común de los números \(a\) y \(b\) y
\(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\).
Determinamos: \(\mathbf{mcd}(4,22)=2\). Como 2|46, la ecuación tiene solución. Para resolverla necesitamos una solución de \(4x_0+22y_0=2\), por ejemplo \((6,-1)\) (si la solución no se aprecia de forma sencilla, podemos utilizar la solución de Bézout). Ahora estamos en condiciones de aplicar el Teorema:
\[\begin{align*}
x&=6\cdot\frac{46}{2}+\frac{22}{2}k=138+11k \\
y&=-1\cdot\frac{46}{2}-\frac{4}{2}k=-23-2k
\end{align*}\]
Ejercicio: Resolver la ecuación diofántica \(6x+15y=36\).
Determinamos: \(\mathbf{mcd}(6,15)=3\). Como 3|36, la ecuación tiene solución. Para resolverla necesitamos una solución de \(6x_0+15y_0=3\), por ejemplo \((-2,1)\). Ahora estamos en condiciones de aplicar el Teorema:
\[\begin{align*}
x&=-2\cdot\frac{36}{3}+\frac{15}{3}k=-24+5k \\
y&=1\cdot\frac{36}{3}-\frac{6}{3}k=12-2k
\end{align*}\]
Observemos el siguiente detalle, si hacemos el cambio \(k=n+5\) será
\[\begin{align*}
x&=-24+5k=-24+5(n+5)=1+5n \\
y&=12-2k= 12-2(n+5)=2-2n
\end{align*}\]
Ejercicio: Sea \(v\) la menor de las soluciones positivas de 34x-56y=4, ¿cuál es el valor de [3,-4].v?
Primero vemos que \[34x-56y=4\Leftrightarrow 34x+56(-y)=4\Leftrightarrow 34x+56z=4 \] donde \(z=-y\). Resolvamos, ahora, \[34x+56z=4\] Determinamos: \(\mathbf{mcd}(34,56)=2\). Como 2|4, la ecuación tiene solución. Para resolverla necesitamos una solución de \(34x_0+56z_0=2\), por ejemplo \((5,-3)\). Ahora estamos en condiciones de aplicar el Teorema:
\[\begin{align*}
x&=5\cdot\frac{4}{2}+\frac{56}{2}k=10+28k \\
z&=-3\cdot\frac{4}{2}-\frac{34}{2}k=-6-17k
\end{align*}\]
Como \(z=-y\) será \(y=-z\), luego
\[\begin{align*}
x&=10+28k \\
y&=6+17k
\end{align*}\]
Obviamente, la primera solución positiva será para \(k=0\), luego \(v=[10,6]\). Por tanto la respuesta es: \[[3,-4].[10,6]=6\]
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?
Calculemos el máximo común divisor:
cociente
-1
-2
1
2
2
48
-27
21
15
6
3
resto
21
15
6
3
0
Observemos que \(\text{mcd}(48,-27)=3\), y \((4)48+(7)(-27)=3\), luego \(x_0=4\), \(y_0=7\)
\[\begin{array}{ccc}\begin{array}{l}x=4\cdot \frac{129}{3}+\frac{(-27)}{3} k\\ y=7\cdot \frac{129}{3}-\frac{48}{3} k\end{array}& \to & \begin{array}{l}x=172+(-9) k \\ y=301-16 k\end{array} \end{array}\]
Como buscamos la solución cuya \(y_s\) negativa sea más próxima a cero, elegimos \(k=\left \lfloor \frac{301}{16}\right \rfloor=18\)
\[\begin{array}{c|c|c|c}
k & 18 & 19 & 20 \\ \hline
x & 10 & 1 & -8 \\
y & 13 & -3 & -19
\end{array}\]
Luego, concluimos que [1,-3].[1,-2]=7.
Ejercicio: Si 10=A, 11=B, 12=C, 13=D, 14=E, ¿cuál carácter no aparece en la representación de \((F_5)_{10}\) en base 15?
A
B
C
B.)
Si realizamos el algoritmo de la división:
\[\begin{align*}
4294967297&=(286331153)15+2\\
286331153&=(19088743)15+8\\
19088743&=(1272582)15+D\\
1272582&=(84838)15+C\\
84838&=(5655)15+D\\
5655&=(377)15+0\\
377&=(25)15+2\\
25&=(1)15+A\\
1&=(0)15+1\\
\end{align*}\]