Archivo de la etiqueta: máximo común divisor

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros $a$ y $b$ para encontrar su máximo común divisor de dos enteros positivos $a$ y $b$.

Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros $a$ y $b$ como combinación lineal de ellos, es decir, de la forma $ra+sb$ con $r$ y $s$ números enteros.

El procedimiento del algoritmo de Euclides

Sean $a, b$ cualesquiera enteros positivos, con $a \neq b$ y $a > b.$ Por el algoritmo de la división, sabemos que siempre existen $q, r \in \mathbb{Z}$ tales que podemos escribir $$a = bq + r, \enspace \text{con} \quad \quad 0 \leq r < b. $$

Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\enspace \text{con} \quad \quad 0 \leq r_1 < r.$$

Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \in \mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\enspace \text{con} \quad \quad 0 \leq r_2 < r_1.$$

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\ldots \geq 0$, de modo que debe existir una $i$ tal que $r_i=0$. De esta forma, en el penúltimo paso tendremos que existen $q_{i-1}$ y $r_{i-1}$ enteros tales que $$r_{i-3} = r_{i-2}q_{i-1} + r_{i-1}, \enspace \text{con} \quad \quad 0 \leq r_{i-1} < r_{i-2}.$$

Y en el último paso tendríamos $q_i \in \mathbb{Z}^+$ y $r_i = 0$ tales que
$$r_{i-2} = r_{i-1}q_i + 0, \enspace \text{con} \quad \quad 0 = r_i < r_{i-1} .$$

Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso $r_{i-1}$ es el máximo común divisor de $a$ y $b$.

Este procedimiento es particularmente útil cuando $a$ y $b$ son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.

Ejemplo del algoritmo de Euclides

A continuación veremos el algoritmo de Euclides en acción.

Problema. Encuentra el máximo común divisor de $3456$ y $6524$.

Solución. Observamos que $6524 > 3456$. Así, $$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
Siguiendo este procedimiento,
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Como el último residuo no cero es $4$, entonces $(6524, 3456)=4$.

$\triangle$

Observación. Aunque el algoritmo de Euclides requiere que los números $a$ y $b$ sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.

Veamos un ejemplo que usa esta observación.

Ejemplo. Obtén el máximo común divisor de $-100$ y $45$.

Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ Le aplicamos el algoritmo de Euclides a estos números:
$$ 100 = 45 \cdot 2 + 10, \quad \quad 0 \leq 10 < 45. $$
$$ 45 = 10 \cdot 4 + 5, \quad \quad 0 \leq 5 < 10. $$
$$10 = 5 \cdot 2 + 0.$$

Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100, 45) = 5.$

$\triangle$

Demostración de la validez del algoritmo de Euclides

Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.

Proposición. Sean $a,b \in \mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $(a,b) = (b,r).$

Demostración. Sean $a,b \in \mathbb{Z}^+$. Sea $d=(a,b)$ el máximo común divisor de $a$ y $b$, y sea $f=(b,r)$ el máximo común divisor de $b$ y $r$.

Tenemos que $d\mid a$. Además, $d \mid b,$ por lo que $d\mid bq$. Así, $d\mid a-bq=r$. De este modo, $d$ es un divisor común de $b$ y de $r$, de modo que $d\mid f$.

Por otro lado, $f\mid b$, de donde $f\mid bq$. Además, $f\mid r$. De este modo, $f\mid bq+r=a$. Concluimos entonces que $f$ es divisor común de $a$ y $b$. Pero entonces $f\mid d$.

Por propiedades de divisibilidad, tenemos entonces que $|f|=|d|$, pero como ambos son números no negativos concluimos entonces que $f=d$, como queríamos.

$\square$

Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.

Teorema. Empecemos tomando dos enteros positivos $a$ y $b$, con $a\geq b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\ldots,r_i$ y $q_0,q_1,\ldots,q_i$ de manera que se cumpla

\begin{align*}
b=aq_0+r_0\\
a=r_0q_1+r_1
\end{align*}

con $0\leq r_0<a$, y $0\leq r_1 < r_0$ y para $j=2,\ldots,i$ que se cumpla

\begin{align*}
r_{j-2}=r_{j-1}q_j+r_{j},
\end{align*}

con $0\leq r_j < r_{j-1}.$

Como $b\geq a > r_0 > r_1 > r_2 > \ldots > r_i$, entonces podemos suponer que $r_i=0$. Entonces $(a,b)=r_{i-1}$.

Demostración. Por la proposición anterior, tenemos que $(a,b)=(b,r_0)$. También por esa misma proposición, tenemos que $(b,r_0)=(r_0,r_1)$. Y, de hecho, aplicando repetidamente la proposición tenemos que:

$$(r_0,r_1)=(r_1,r_2)=\ldots=(r_{i-1},r_i)=(r_{i-1},0)=r_{i-1}.$$

La penúltima igualdad es porque $r_i=0$ y la última porque $(n,0)=n$ para cualquier entero positivo $n$.

$\square$

Máximo común divisor como combinación lineal entera

Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números $a$ y $b$ como combinación lineal entera de ellos dos.

Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar $(6524,3456)$.

$$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con $1,0$ y la segunda con $0,1$.

$6524$$1$$0$
$3456$$0$$1$
$3068$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que $3456$ cabe $1$ vez en $6524$. Por esta razón, restamos $1$ vez la segunda fila de la primera, para obtener $1-0=1$ y $0-1=-1$. Estos son los números que van en la fila $3$, columnas $2$ y $3$:

$6524$$1$$0$
$3456$$0$$1$
$3068$$\mathbf{1}$$\mathbf{-1}$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

De nuevo, $3068$ cabe una vez en $3456$, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda $0-1=-1$ y $1-(-1)=2$ para las nuevas entradas:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$\mathbf{-1}$$\mathbf{2}$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Ahora cambia un poco, pues $388$ ya sabemos que cabe $7$ veces en $3068$ (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números $1-7\cdot (-1)=8$ y $-1-7\cdot (2)=-15$. La tabla queda así:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$\mathbf{8}$$\mathbf{-15}$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$8$$-15$
$36$$-9$$17$
$28$$89$$-168$
$8$$-98$$185$
$4$$383$$-723$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a $4$ como combinación lineal entera de $6524$ y de $3456$:

$$4=383 \cdot 6524 – 723 \cdot 3456.$$

Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.

¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas $a,b,c$ se cumple que $a=6524b+3456c$. Esto queda como uno de los problemas de tarea moral.

Más adelante…

Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo $n$, lo cual nos ayudará a formalizar estas ideas.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
    1. $15$ y $35$
    2. $18$ y $92$
    3. $201$ y $153$
    4. $328$ y $528$
  2. ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números $91$, $105$ y $119$? Es decir, debes encontrar el mayor entero $d$ que divida a estos tres números de manera simultánea.
  3. Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números $n$ y $m$ y que, conjuntamente, usan los números primos distintos $p_1,p_2,\ldots, p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
    \begin{align*} m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\ \end{align*}.
    1. Demuestra que la máxima potencia de $p_1$ que divide tanto a $m$ como a $n$ es $p_1^{\text{min}(\alpha_1,\beta_1)}$.
    2. Demuestra que el máximo común divisor de $m$ y $n$ es $$p_1^{\text{min}(\alpha_1,\beta_1)} p_2^{\text{min}(\alpha_2,\beta_2)}\cdots p_k^{\text{min}(\alpha_k,\beta_k)}.$$
  4. Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y usa ambos resultados para dar otra demostración de que $(m,n)[m,n]=mn$.
  5. Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Mínimo común múltiplo

Por Ana Ofelia Negrete Fernández

Deja un comentario

Introducción

En la entrada anterior hablamos del máximo común divisor, para lo cual lo definimos en términos de ideales. Luego vimos que cumplía las propiedades que esperábamos. Es el turno de hacer lo mismo con el mínimo común múltiplo.

Recordando lo que nos enseñaron en la educación básica, el mínimo común múltiplo de dos enteros $a$ y $b$ tenía que ser simultáneamente múltiplo de ambos y, a la vez, tenía que ser lo más pequeño posible. Siendo un poco más precisos, tenía que ser un múltiplo positivo.

Como ejemplo, tomemos $a = 6$, $b = 8$. Una manera muy sencilla de encontrar un múltiplo en común es multiplicando ambos: $6\cdot 8 = 48$. Pero este no es el múltiplo más pequeño. Para poder encontrar aquel que sí sea el más pequeño, podemos enlistar los múltiplos de cada uno de estos números:

  • Múltiplos de $6$: $6,12,18,24,30,36, \ldots$
  • Múltiplos de $8$: $8, 16, 24, 32, 40, \ldots$

Notamos que el número más pequeño que está en ambas listas es el $24$. En educación básica había otras maneras de obtener esto sin hacer las listas anteriores, por ejemplo, mediante la siguiente tabla, en donde «vamos encontrando divisores en común, o bien de cada número».

862
432
232
133
1
El mínimo común múltiplo de 8 y 6 es $2^3\cdot 3 = 24.$

Lo que haremos será un poco distinto. Nuestra definición se basará nuevamente en el concepto de ideales. Veremos cómo hacer esto y cómo regresar al terreno familiar de mínimo común múltiplo que ya conocemos.

Mínimo Común Múltiplo

En la entrada de ideales en $\mathbb{Z}$ demostramos que la intersección de cualesquiera dos ideales es un ideal. También vimos que cualquier ideal era generado por algún entero no negativo. Esto nos lleva a la siguiente definición.

Definición. Sean $a$ y $b$ números enteros. Definimos a su mínimo común múltiplo como al entero no negativo $k$ tal que $a\mathbb{Z} \cap b\mathbb{Z} = k \mathbb{Z}$. En símbolos, nos referimos al mínimo común múltiplo de $a$ y $b$ como $\text{mcm}(a,b)$, o bien simplemente como $[a,b]$.

Ejemplo. Retomemos el ejemplo de la introducción. Si queremos calcular, por definición, al mínimo común múltiplo de los enteros $6$ y $8$, debemos considerar a los ideales $6\mathbb{Z}$ y $8\mathbb{Z}$, que respectivamente son:

$$6 \mathbb{Z} = \{\ldots, -12, -6, 0, 6, 12 ,18, 24, \ldots \}$$

$$8 \mathbb{Z}= \{\ldots, -16, -8, 0 ,8, 16, 24, 32, \ldots \}$$

Si hacemos la intersección de ambos ideales, notemos que obtenemos lo siguiente:

$$6 \mathbb{Z} \cap 8 \mathbb{Z} = \{\ldots, -24, 0, 24, 48, 72, \ldots\},$$

que es el ideal generado por el $24$. Así, tenemos, por definición, que el mínimo común múltiplo de $6$ y $8$ es igual a $24$.

$\triangle$

Propiedad fundamental del mínimo común múltiplo

Lo que nos gustaría hacer ahora es demostrar que el mínimo común múltiplo que obtuvimos de nuestra definición es, en efecto, el número que cumple con las propiedades que esperamos. Escribimos esto en la siguiente proposición.

Proposición. Sean $a$ y $b$ números enteros. Se cumple que:

  • $a\mid [a,b]$ y $b\mid [a,b]$
  • Si $a\mid m$ y $b\mid m$, entonces $[a,b]\mid m$.

Demostración. La primera parte es sencilla. Como $[a,b]$ genera a $a\mathbb{Z} \cap b \mathbb{Z}$, en particular está en este conjunto. Como $[a,b]\in a\mathbb{Z}$, entonces $a|[a,b]$ y como $[a,b]\in b\mathbb{Z}$, entonces $b|[a,b]$.

Para la segunda parte, si $a\mid m$ y $b\mid m$, entonces $m\in a\mathbb{Z}$ y $m\in b\mathbb{Z}$, pero entonces $m\in a\mathbb{Z} \cap b\mathbb{Z} = [a,b]\mathbb{Z}$. De este modo, $[a,b]|m$.

$\square$

Así, el primer punto dice que $[a,b]$ es en efecto un múltiplo en común. El segundo punto es el que dice que «es el mínimo», pues a partir de la divisibilidad ahí escrita se deduce que $|[a,b]|\leq |m|$. Si pedimos que $m$ sea positivo, tenemos entonces que, en efecto, $[a,b]\leq m$. En resumen.

Corolario. Sean $a$ y $b$ enteros y $m$ un entero positivo múltiplo tanto de $a$ como de $b$. Entonces $m\geq [a,b]$.

Otra propiedad del mínimo común múltiplo

Tanto el mínimo común múltiplo, como el máximo común divisor, tienen muchas propiedades que se pueden demostrar. Hay dos caminos que usualmente funcionan: o bien usar la definición a partir de ideales, o bien usar las propiedades fundamentales de cada uno de los conceptos. Veamos algunos ejemplos para el mínimo común múltiplo.

La siguiente propiedad dice que ahora mostraremos que el mínimo común múltiplo «saca constantes» en cierto sentido. Veremos una demostración usando ideales.

Proposición. Sea $k$ un entero positivo, y $b,c$ enteros cualesquiera. Se cumple que $ [kb, kc] = k[b,c]. $

Demostración. Por definición, $[kb,kc]$ es el entero no negativo que genera al ideal $(kb)\mathbb{Z} \cap (kc)\mathbb{Z}$. Nos gustaría ver que dicho entero es $k[b,c]$, en otras palabras, hay que verificar la siguiente igualdad de conjuntos:

$$(kb)\mathbb{Z} \cap (kc)\mathbb{Z} = k[b,c]\mathbb{Z}.$$

Veamos que el lado izquierdo está contenido en el derecho. Tomemos un entero $m$ del lado izquierdo. Como es múltiplo de $kb$, lo podemos escribir como $m=kbr$ para $r \in \mathbb{Z}$. Como es múltiplo de $kc$, lo podemos escribir como $m=kcs$ para $s\in \mathbb{Z}$. Tenemos entonces $kbr=m=kcs$, de donde $br=cs$ (usando $k>0$). Así, $n=br=cs$ es simultánteamente múltiplo de $b$ y $c$, así que debe ser múltiplo de $[b,c]$, digamos $n=t[b,c]$. De este modo, tenemos que $m=kbr=kn=kt[b,c]$. Esto muestra que $m$ está en $k[b,c]\mathbb{Z}$.

Ahora veamos que el lado derecho está contenido en el izquierdo. Un entero $m$ en $k[b,c]\mathbb{Z}$ es de la forma $m=k[b,c]t$ para $t$ un entero. Como $[b,c]$ es múltiplo de $b$ y $c$, podemos escribir $[b,c]=rb$ y $[b,c]=sc$ para algunos enteros $r$ y $s$. Tenemos entonces que

$$m=k[b,c]t=krbt=(kb)(rt),$$

lo cual muestra que $m$ está en $(kb)\mathbb{Z}$ y que

$$m=k[b,c]t=ksct=(kc)(st),$$

lo cual muestra que $m$ está en $(kc)\mathbb{Z}$. Esto muestra que $m$ está en la intersección buscada.

$\square$

Mínimo común múltiplo y primos relativos

Cuando dos números positivos son primos relativos, es sencillo encontrar su mínimo común múltiplo: simplemente se multiplican. De hecho, esto es una caracterización para los números primos relativos.

Proposición. Sean $a$ y $b$ dos números enteros positivos. Se tiene que $(a,b)=1$ si y sólo si $[a,b]=ab$.

Demostración. Supongamos primero que $(a,b)=1$. Tenemos que $a|[a,b]$ y que $b|[a,b]$ Por una propiedad de primos relativos de la entrada anterior, podemos deducir que $ab|[a,b]$. A la vez, sabemos que $[a,b]$ divide a cualquier múltiplo en común de $a$ y $b$, en particular, a $ab$, así, $[a,b]|ab$. Por cómo interactúa la divisibilidad con los valores absolutos, obtenemos entonces que $[a,b]=|[a,b]|=ab$, como queríamos.

Ahora supongamos que $[a,b]=ab$. Tomemos un número $d$ que divida tanto a $a$ como a $b$. Veremos que ese número debe ser $1$ ó $-1$. Escribamos $a=dr$ y $b=ds$. Tomemos el número $n=drs$. Notemos que $n=as=br$, así que $n$ es un múltiplo común de $a$ y $b$. Por ello, debe ser múltiplo del mínimo común múltiplo de ambos, que estamos suponiendo que es $ab$. Así, existe un entero $k$ con $drs=kab$ y por lo tanto $$drs=kab=kdrds.$$ De aquí deducimos que $1=kd$, por lo que $d$ debe de dividir a $1$ y por lo tanto es $1$ ó $-1$, como queríamos.

$\square$

En realidad esta proposición tiene una versión más general. Siempre se cumple, para cualesquiera dos enteros $a$ y $b$, que $|ab|=[a,b]\cdot (a,b)$. Este es un problema clásico que estudiaremos más adelante.

Más adelante…

El mínimo común múltiplo y el máximo común divisor son dos conceptos que se utilizan mucho en la teoría de números enteros. En estas últimas dos entradas hemos platicado un poco acerca de ellos. Más adelante veremos que estas mismas nociones se pueden generalizar para otras estructuras algebraicas, como la de los polinomios.

Por ahora continuaremos estudiando teoría de la divisibiliad dentro de los números enteros. Es el momento de introducir otro de los conceptos estelares: el de números primos.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Encuentra el mínimo común múltiplo de los números $24$ y $36$. Luego, encuentra su máximo común divisor.
  2. Demuestra que, para $a,b\in \mathbb{Z}$ se cumple: $[a,b] = [-a,b] = [a,-b] = [-a, -b].$
  3. Sean $a$ y $b$ enteros positivos. Muestra que $[a^2,b^2]=[a,b]^2$ y que, en general, para un entero $k\geq 1$ se cumple que $[a^n,b^n]=[a,b]^n$.
  4. ¿Cómo definirías el mínimo común múltiplo de tres números? ¿Y el máximo común divisor de tres números?
  5. Sean $a$, $b$, $c$ enteros. ¿Cómo están relacionados entre sí $[a,c]$, $[b,c]$ y $[a+b,c]$? ¿Será alguno de ellos la suma de los otros dos? Demuéstralo o da un contraejemplo.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Máximo común divisor

Por Ana Ofelia Negrete Fernández

Deja un comentario

Introducción

La entrada anterior fue un poco técnica y habló acerca de ideales en los números enteros. Podemos apoyarnos de los ideales para construir otras nociones conocidas de la teoría de números enteros. En esta entrada hablaremos de una de ellas: la de máximo común divisor.

Quizás recuerdes la idea general del máximo común divisor a partir de lo que aprendiste en la educación básica. Por ejemplo, si tenemos a los números $14$ y $35$,y queremos encontrar su máximo común divisor, lo que se hacía es escribir los divisores de ambos:

  • Divisores de $14$: $1,2,7,14$.
  • Divisores de $35$: $1,5,7,35$.

Ya teniendo ambas listas, se elige número más grande que estén en ambas: el $7$.

Con lo que platicaremos en esta entrada vamos a recuperar esta misma noción, sin embargo lo haremos desde un punto de vista un poco más teórico, el cual nos permitirá entender más aspectos de divisibilidad de los máximos comunes divisores.

Definición de máximo común divisor

Recordemos, que en la entrada pasada vimos cómo encontrar al «ideal más pequeño» que tuviera a dos números $a$ y $b$ enteros dados.

Proposición. Si $a$ y $b$ son enteros, entonces:

  • El conjunto $M=\{ra+sb:r,s\in \mathbb{Z}\}$ es un ideal de $\mathbb{Z}$ que tiene a $a$ y a $b$.
  • Si $I$ es un ideal de $\mathbb{Z}$ que tiene a $a$ y a $b$, entonces $M\subseteq I$.

Como $M$ es el ideal más pequeño que tiene a $a$ y a $b$, le llamamos el ideal generado por $a$ y $b$, y lo escribimos como $\langle a,b\rangle$.

Además, en la entrada anterior también vimos que cualquier ideal de $\mathbb{Z}$ forzosamente es de la forma $k\mathbb{Z}$ para algún entero no negativo $k$, es decir, que consiste justo de los múltiplos de algún entero no negativo $k$. Esto nos permite plantear la siguiente definición.

Definición. Si $a$ y $b$ son enteros, definimos a su máximo común divisor como el entero no negativo $k$ tal que $$k\mathbb{Z}=\langle a,b\rangle.$$ A este número $k$ a veces se le denota por $\text{MCD}(a,b)$, o bien simplemente $(a,b)$.

Esta es una definición muy distinta de la que nos dan en la educación básica, sin embargo, pronto recuperaremos las propiedades familiares: veremos que en efecto es un divisor de $a$, es un divisor de $b$, y que de entre los divisores en común, es el más grande de ellos. Antes de pasar a las propiedades, veamos un ejemplo.

Ejemplo. Tomemos a los enteros $6$ y $14$. ¿Qué ideal $I$ generan? Es decir, ¿quién es $\langle 6,8\rangle$? Bueno, dicho ideal $I$ debe tener a $6$ y $14$, así que por cerradura de la resta tiene también a $14-6-8$, y similarmente debe tener a $8-6=2$. Pero recordemos que los ideales también son cerrados bajo producto por cualquier entero, así que al estar $2$ en $I$, debe pasar que todos los números pares están en $I$. Y en efecto, los números pares son un ideal de $\mathbb{Z}$ que tienen a $6$ y $14$. Con esto acabamos de demostrar que $\langle 6,14 \rangle = 2\mathbb{Z}$. De este modo, por definición, el máximo común divisor de $6$ y $14$ es igual a $2$.

$\triangle$

Propiedades del máximo común divisor

En esta sección veremos dos propiedades muy importantes del máximo común divisor. Por un lado, veremos que siempre se puede escribir «como combinación» de los números originales, en un sentido muy específico. Por otro lado, recuperaremos las «propiedades usuales» que queremos que se cumplan por lo que aprendimos en educación básica.

Proposición. Sean $a$ y $b$ números enteros. Entonces, existen enteros $r$ y $s$ tales que $$(a,b)=ra+sb.$$

Demostración. Por definición, $(a,b)$ es el entero tal que $\langle a,b \rangle =(a,b)\mathbb{Z}$, en particular, $(a,b)$ está en $\langle a,b\rangle$. Pero también ya sabemos que $$\langle a,b \rangle = \{ra+sb:r,s\in \mathbb{Z}\}.$$ Como $(a,b)$ está en $\langle a,b \rangle$, entonces se puede escribir de la forma de los elementos del conjunto de la derecha también, es decir, existen enteros $r$ y $s$ tales que $$(a,b)=ra+sb.$$

$\square$

Como estamos poniendo a $(a,b)$ de la forma $ra+sb$, en donde los coeficientes de $a$ y $b$ son los números enteros $r$ y $s$, decimos que $(a,b)$ se puede escribir como una combinación lineal entera de $a$ y $b$. La proposición anterior nos demuestra la existencia de dicha combinación lineal, sin embargo no nos dice exactamente cómo encontrarla. Más adelante veremos el algoritmo de Euclides, el cual nos da una forma práctica de encontrar al máximo común divisor de dos números como combinación lineal de ellos.

Veamos ahora el resultado que nos dice que, en efecto, el máximo común divisor divide a cada número, y que es «el más grande» que hace esto.

Proposición. Sean $a$ y $b$ números enteros. Entonces, se cumple lo siguiente:

  • $(a,b)|a$ y $(a,b)|b$.
  • Si $d$ es algún otro número tal que $d|a$ y $d|b$, entonces $d|(a,b)$.

Demostración. Notemos que $a\in \langle a, b\rangle$, y que por definición $\langle a,b \rangle = (a,b) \mathbb{Z}$. De este modo, $a$ es múltiplo de $(a,b)$. Análogamente, $b$ es múltiplo de $(a,b)$. Esto muestra el primer inciso.

Ahora supongamos que $d$ es otro número tal que $d|a$ y $d|b$. Por la proposición anterior, existen enteros $r$ y $s$ tales que $(a,b)=ra+sb$. Como $d|a$, entonces $d|ra$. Como $d|b$, entonces $d|sb$. Así, $d|ra+sb=(a,b)$, como queríamos.

$\square$

La proposición anterior sí dice que el máximo común divisor divide a ambos, sin embargo no es totalmente directo por qué es el «máximo» en tamaño. La segunda parte habla más bien de una divisibilidad. Pero esto se traduce rápidamente a una desigualdad con la ayuda de las propiedades de la divisibilidad. Observa que si $d$ es un número tal que $d|a$ y $d|b$, entonces $d|(a,b)$. Tenemos entonces que $|d|\leq |(a,b)|$. Pero $(a,b)$ siempre es no negativo por definición, así que $|d|\leq (a,b)$. En resumen, tenemos el siguiente resultado.

Corolario. Si $a$ y $b$ son enteros y $d$ es un entero tal que $d|a$ y $d|b$, entonces $|d|\leq (a,b)$.

Números primos relativos (de máximo común divisor igual a uno)

Una situación muy especial en la teoría de los números ocurre cuando el máximo común divisor de dos números es igual a $1$.

Definición. Decimos que dos números enteros $a$ y $b$ son primos relativos si su máximo común divisor es igual a $1$. En símbolos, son primos relativos si $(m,n)=1$.

Por lo que hemos discutido hasta ahora, algunas de las consecuencias de que dos números $a$ y $b$ sean primos relativos son las siguientes:

  • Si $d$ es un número que divide a $a$ y a $b$, entonces $|d|\leq (a,b)=1$, es decir, $d=1$ o $d=-1$. De este modo, los únicos divisores que tienen en común son el $1$ y el $-1$.
  • El ideal generado por $a$ y $b$ es $1\cdot \mathbb{Z} = \mathbb{Z}$, es decir, consiste de todos los enteros.
  • Por esa misma razón, se tiene que $\{ra+sb: r,s \in \mathbb{Z}\}=\mathbb{Z}$, en otras palabras, cualquier entero es combinación lineal entera de $a$ y de $b$.
  • En particular, el $1$ es combinación lineal entera de $a$ y de $b$, es decir, existen enteros $r,s$ tales que $ra+sb=1$.

Estas consecuencias son prácticamente inmediatas de la definición, y es recomendable que intentes deducirlas por tu cuenta.

Veamos algunas otras propiedades que relacionan a los números primos relativos, con divisibilidad de algunas expresiones.

Proposición. Sean $a,b,c$ números enteros . Si $a\mid bc$ y $(a,b) = 1$, entonces $a\mid c.$

Demostración. Como $a$ divide a $bc$, existe $x \in \mathbb{Z}$ tal que $ax = bc$. Como $a$ y $b$ son primos relativos, sabemos que existen enteros $r$ y $s$ tales que $1 = ra+sb$. Multipliquemos esta última igualdad por $c$. Tenemos entonces que:
$$ c = rac + sbc = rac+ sax = a (rc+sx).$$

De aquí obtenemos la divisibilidad $a\mid c$ que buscábamos.

$\square$

En la proposición anterior es crucial la hipótesis de que $a$ y $b$ sean primos relativos. Por ejemplo, $7|28=14\cdot 2$, pero no pasa que $7|2$. Es decir, usualmente si dividimos a un producto, no se cumple que dividamos a cualquiera de sus factores.

A continuación tenemos otro resultado con un estilo similar.

Proposición. Sean $a,b,c \in \mathbb{Z}.$ Si $a\mid c$, $b\mid c$ y $(a,b) =1,$ entonces $ab \mid c$.

Demostración. Ya que $a,b$ son primos relativos, existen $m,n \in \mathbb{Z}$ tales que $1=am + bn $. Multipliquemos dicha ecuación por $c$: $$c=cam + cbn.$$

Como $a\mid c$ y $b\mid c$, existen $q,r \in \mathbb{Z}$ tales que $aq = c$ y $br = c$. Sustituyendo esto en la ecuación anterior, obtenemos que: $$c=cam + cbn = bram + aqbn = ab(rm+qn).$$

Esta igualdad justo nos dice que $ab\mid c$, como queríamos.

$\square$

Intenta encontrar un contraejemplo cuando no se cumple la hipótesis de que $a$ y $b$ son números primos relativos.

Más adelante…

Dejaremos el estudio del máximo común divisor hasta aquí por el momento. En la siguiente entrada hablaremos de un concepto muy cercano: el de mínimo común múltiplo. Así como en el caso de esta entrada, introduciremos la noción a partir de un contexto de ideales, para luego ver ejemplos y algunas propiedades clave.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra todas las consecuencias de ser primos relativos de la lista enunciada en la entrada.
  2. Prueba que dos enteros consecutivos siempre son primos relativos. Usa esto para demostrar que siempre que se eligen $51$ números distintos entre $1$ y $100$, forzosamente debes tener dos de ellos que sean primos relativos.
  3. Sea $m$ un entero positivo. Demuestra que $(a,b)=1$ si y sólo si $(a^m, b^m) =1.$
  4. De acuerdo a la entrada, al tomar dos números $a$ y $b$ podemos encontrar enteros $r$ y $s$ tales que $(a,b)=ra+sb$. Demuestra que siempre sucede que $(r,s)=1$.
  5. Encuentra el máximo común divisor de $91$ y $70$ e intenta escribirlo como combinación lineal entera de ellos.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Máximo común divisor de polinomios y algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En esta entrada continuamos estudiando propiedades aritméticas del anillo de polinomios con coeficientes reales. En la entrada anterior introdujimos el algoritmo de la división, la noción de divisibilidad y los polinomios irreducibles. Además, mostramos el teorema del factor y el teorema del residuo. Lo que haremos ahora es hablar del máximo común divisor de polinomios.

Mucha de la teoría que desarrollamos en los enteros también se vale para $\mathbb{R}[x]$. Como en $\mathbb{Z}$, lo más conveniente para desarrollar esta teoría es comenzar hablando de ideales. Con estos buenos cimientos, veremos que el máximo común divisor de dos polinomios se puede escribir como «combinación lineal de ellos». Para encontrar la combinación lineal de manera práctica, usaremos de nuevo el algoritmo de Euclides.

Antes de comenzar, haremos una aclaración. Hasta ahora hemos usado la notación $f(x), g(x),h(x)$, etc. para referirnos a polinomios. En esta entrada frecuentemente usaremos nada más $f,g,h$, etc. Por un lado, esto simplificará los enunciados y demostraciones de algunos resultados. Por otro lado, no corremos el riesgo de confusión pues no evaluaremos a los polinomios en ningún real.

Ideales de $\mathbb{R}[x]$

Comenzamos con la siguiente definición clave, que nos ayuda a hacer las demostraciones de máximo común divisor de polinomios de manera más sencilla.

Definición. Un subconjunto $I$ de $\mathbb{R}[x]$ es un ideal si pasa lo siguiente:

  1. El polinomio cero de $\mathbb{R}[x]$ está en $I$.
  2. Si $f$ y $g$ son elementos de $\mathbb{R}[x]$ en $I$, entonces $f+g$ está en $I$.
  3. Si $f$ y $g$ son elementos de $\mathbb{R}[x]$, y $f$ está en $I$, entonces $fg$ está en $I$.

Ejemplo 1. El conjunto $I_0=\{f\in \mathbb{R}[x]\mid f(0)=0 \}$.

Evidentemente el polinomio constante $0$, está en $I_0$, ya que evaluado en cualquier número es cero (en particular al evaluarlo en 0).

Si $f,g\in I_0$, entonces $(f+g)(0)=f(0)+g(0)=0+0=0$, por lo que $f+g\in I_0$.

Finalmente, si $g\in I_0$ y $f$ es cualquier polinomio, tenemos que $(fg)(0)=f(0)g(0)=f(0)\cdot 0=0$, por lo que $fg\in I_0$. Con esto concluimos que $I_0$ es un ideal.

$\triangle$

Al igual que en los enteros, los únicos ideales consisten de múltiplos de algún polinomio. El siguiente resultado formaliza esto.

Teorema (caracterización de ideales en $\mathbb{R}[x]$). Un subconjunto $I$ es un ideal de $\mathbb{R}[x]$ si y sólo si existe un polinomio $f$ tal que $$I=f\mathbb{R}[x]:=\{fg: g \in \mathbb{R}[x]\}.$$

Demostración de «la ida». Primero mostraremos que cualquier conjunto de múltiplos de un polinomio dado $f$ es un ideal. Tomemos $f$ en $\mathbb{R}[x]$ y $$I=f\mathbb{R}[x]=\{fg: g \in \mathbb{R}[x]\}.$$

La propiedad (1) de la definición de ideal se cumple pues tomando $g=0$ tenemos que $f\cdot 0 = 0$ está en $I$.

Para la propiedad (2), tomamos $fg_1$ en $I$ y $fg_2$ en $I$, es decir, con $g_1$ y $g_2$ en $\mathbb{R}[x]$. Su suma es, por la ley de distribución, el polinomio $f\cdot (g_1+g_2)$, que claramente está en $I$ pues es un múltiplo de $f$.

Para la propiedad (3), tomamos $fg$ en $I$ y $h$ en $\mathbb{R}[x]$. El producto $(fg)\cdot h$ es, por asociatividad, igual al producto $f\cdot(gh)$, que claramente está en $I$. De esta forma, $I$ cumple (1), (2) y (3) y por lo tanto es un ideal.

$\square$

Demostración de «la vuelta». Mostraremos ahora que cualquier ideal $I$ es el conjunto de múltiplos de un polinomio. Si $I=\{0\}$, que sólo tiene al polinomio cero, entonces $I$ es el conjunto de múltiplos del polinomio $0$. Así, podemos suponer que $I$ tiene algún elemento que no sea el polinomio $0$.

Consideremos el conjunto $A$ de naturales que son grado de algún polinomio en $I$. Como $I$ tiene un elemento no cero, $A$ es no vacío. Por el principio del buen orden, $A$ tiene un mínimo, digamos $n$. Tomemos en $I$ un polinomio $f$ de grado $n$. Afirmamos que $I$ es el conjunto de múltiplos de $f$, es decir, $$I=f\mathbb{R}[x].$$

Por un lado, como $f$ está en $I$ e $I$ es un ideal, por la propiedad (3) de la definición de ideal se tiene que $fg$ está en $I$ para todo $g$ en $\mathbb{R}[x]$. Esto muestra la contención $f\mathbb{R}[x]\subseteq I$.

Por otro lado, supongamos que hay un elemento $h$ que está en $I$, pero no es múltiplo de $f$. Por el algoritmo de la división, podemos encontrar polinomios $q$ y $r$ tales que $h-qf=r$ y $r$ es el polinomio cero o de grado menor a $f$. No es posible que $r$ sea el polinomio cero pues dijimos que $h$ no es múltiplo de $f$. Así, $r$ no es el polinomio cero y su grado es menor al de $f$.

Notemos que $-qf$ está en $I$ por ser un múltiplo de $f$ y que $h$ está en $I$ por cómo lo elegimos. Por la propiedad (2) de la definición de ideal se tiene entonces que $r=h+(-qf)$ también está en $I$. Esto es una contradicción, pues habíamos dicho que $f$ era un polinomio de grado mínimo en $I$, pero ahora $r$ tiene grado menor y también está en $I$. Por lo tanto, es imposible que exista un $h$ en $I$ que no sea múltiplo de $f$. Esto muestra la contención $I\subseteq f\mathbb{R}[x]$.

$\square$

Ejemplo 2. En el ejemplo anterior, $I_0$ denotaba el conjunto de polinomios que se anulan en $0$, podemos demostrar que $I_0=x\mathbb{R}[x]$, ya que si $f\in I_0$, por el teorema del factor, el polinomio $x-0$ divide a $f$, es decir que $f(x)=xg(x)$ para alguan $g\in \mathbb{R}[x]$. Esto prueba que $I_0\subseteq x\mathbb{R}$, dejamos el resto de los detalles como un ejercicio moral.

$\triangle$

El teorema anterior nos dice que cualquier ideal se puede escribir como los múltiplos de un polinomio $f$. ¿Es cierto que este polinomio $f$ es único? Para responder esto, pensemos qué sucede si se tiene $$f\mathbb{R}[x]=g\mathbb{R}[x],$$ o, dicho de otra forma, pensemos qué sucede si $f$ divide a $g$ y $g$ divide a $f$.

Si alguno de $f$ ó $g$ es igual a $0$, entonces el otro también debe de serlo. Así, podemos suponer que ninguno de ellos es igual a $0$. Como $g$ divide a $f$, podemos escribir a $f$ como $hg$ para $h$ un polinomio no cero. De manera similar, podemos escribir a $g$ como un polinomio $kf$ para $k$ un polinomio no cero. Pero entonces $$f=hg=hkf.$$

El grado del lado izquierdo es $\deg(f)$ y el del derecho es $\deg(h)+\deg(k)+\deg(f)$, de donde obtenemos que $\deg(h)=\deg(k)=0$. En otras palabras, concluimos que $h$ y $k$ son polinomios constantes y distintos de cero. Resumimos esta discusión a continuación.

Proposición. Tomemos $f(x)$ y $g(x)$ polinomios en $\mathbb{R}[x]$ distintos del polinomio $0$. Si $f(x)$ divide a $g(x)$ y $g(x)$ divide a $f(x)$, entonces $f(x)=hg(x)$ para un real $h\neq 0$. Del mismo modo, si $f(x)=hg(x)$ con $h$ un real, entonces $f(x)$ divide a $g(x)$ y $g(x)$ divide a $f(x)$.

Cuando sucede cualquiera de las cosas de la proposición anterior, decimos que $f(x)$ y $g(x)$ son asociados.

Ya que no hay un único polinomio que genere a un ideal, nos conviene elegir a uno de ellos que cumpla una condición especial. El coeficiente principal de un polinomio es el que acompaña al término de mayor grado. En otras palabras, si $p(x)$ es un polinomio de grado $n$ dado por $$p(x)=a_0+\ldots+a_nx^n,$$ con $a_n\neq 0$, entonces $a_n$ es coeficiente principal.

Definición. Un polinomio es mónico si su coeficiente principal es $1$.

Por la proposición anterior, existe un único polinomio mónico asociado a $p(x)$, y es $\frac{1}{a_n}p(x)$. Podemos resumir las ideas de esta sección mediante el siguiente teorema.

Teorema. Para todo ideal $I$ de $\mathbb{R}[x]$ distinto del ideal $\{0\}$, existe un único polinomio mónico $f$ tal que $I$ es el conjunto de múltiplos de $f$, en símbolos, $$I=f\mathbb{R}[x].$$

Máximo común divisor de polinomios

Tomemos $f$ y $g$ polinomios en $\mathbb{R}[x]$. Es sencillo ver, y queda como tarea moral, que el conjunto $$f\mathbb{R}[x]+g\mathbb{R}[x]=\{rf+sg: r,s \in \mathbb{R}[x]\}$$ satisface las propiedades (1), (2) y (3) de la definición de ideal. Por el teorema de caracterización de ideales, la siguiente definición tiene sentido.

Definición. El máximo común divisor de $f$ y $g$ es el único polinomio mónico $d$ en $\mathbb{R}[x]$ tal que $$f\mathbb{R}[x]+g\mathbb{R}[x] = d\mathbb{R}[x].$$ A este polinomio lo denotamos por $\MCD{f,g}$.

De manera inmediata, de la definición de $\MCD{f,g}$, obtenemos que es un elemento de $f\mathbb{R}[x]+g\mathbb{R}[x]$, o sea, una combinación lineal polinomial de $f$ y $g$. Este es un resultado fundamental, que enunciamos como teorema.

Teorema (identidad de Bézout). Para $f$ y $g$ en $\mathbb{R}[x]$ existen polinomios $r$ y $s$ en $\mathbb{R}[x]$ tales que $$\MCD{f,g}=rf+sg.$$

El nombre que le dimos a $\MCD{f,g}$ tiene sentido, en vista del siguiente resultado.

Teorema. Para $f$ y $g$ en $\mathbb{R}[x]$ distintos del polinomio cero se tiene que:

  • $\MCD{f,g}$ divide a $f$ y a $g$.
  • Si $h$ es otro polinomio que divide a $f$ y a $g$, entonces $h$ divide a $\MCD{f,g}$.

Demostración. Por definición, $$f\mathbb{R}[x]+g\mathbb{R}[x] = \MCD{f,g}\mathbb{R}[x].$$ El polinomio $f$ pertenece al conjunto del lado izquierdo, pues lo podemos escribir como $$1\cdot f + 0 \cdot g,$$ así que también está en el lado derecho. Por ello, $f$ es un múltiplo de $\MCD{f,g}$. De manera similar se prueba que $g$ es un múltiplo de $\MCD{f,g}$.

Para la segunda parte, escribimos a $\MCD{f,g}$ como combinación lineal polinomial de $f$ y $g$, $$\MCD{f,g}=rf+sg.$$ De aquí es claro que si $h$ divide a $f$ y a $g$, entonces $h$ divide a $\MCD{f,g}$.

$\square$

Todo esto va muy bien. El máximo común divisor de dos polinomios en efecto es un divisor, y es «el mayor», en un sentido de divisibilidad. Además, como en el caso de $\mathbb{Z}$, lo podemos expresar como una combinación lineal de sus polinomios. En la tarea moral puedes ver algunos ejemplos que hablan del concepto dual: el mínimo común múltiplo.

El algoritmo de Euclides

Al igual que como sucede en los enteros, podemos usar el algoritmo de la división iteradamente para encontrar el máximo común divisor de polinomios, y luego revertir los pasos para encontrar de manera explícita al máximo común divisor como una combinación lineal polinomial de ellos. Es un buen ejercicio enunciar y demostrar que esto es cierto. No lo haremos aquí, pero veremos un ejemplo de cómo aplicar el algoritmo.

Problema: Encuentra el máximo común divisor de los polinomios
\begin{align*}
a(x)&=x^7+x^6+x^5+x^4+x^3+x^2+x+1\\
b(x)&=x^4+x^3+x^2+x+1,
\end{align*} y exprésalo como combinación lineal de $a(x)$ y $b(x)$.

Solución. Aplicando el algoritmo de la división repetidamente, tenemos lo siguiente:

\begin{align*}
a(x)&=x^3b(x)+(x^2+x+1)\\
b(x)&=x^2(x^2+x+1)+(x+1)\\
x^2+x+1&=x(x+1)+1.
\end{align*}

Esto muestra que $a(x)$ y $b(x)$ tienen como máximo común divisor al polinomio $1$. Por lo que discutimos antes, debe haber una combinación lineal polinomial de $a(x)$ y $b(x)$ igual a $1$ Para encontrarla de manera explícita, invertimos los pasos:

\begin{equation*}
\begin{split}
1 & =(x^2+x+1)-x(x+1)\\
& =(x^2+x+1)-x(b(x)-x^2(x^2+x+1))\\
& =(x^2+x+1)(x^3+1)-xb(x)\\
& =(x^3+1)(a(x)-x^3(b(x))-xb(x)\\
& =(x^3+1)a(x)-x^3(x^3+1)b(x)-xb(x)\\
& =(x^3+1)a(x)+(-x^6-x^3-x)b(x)
\end{split}
\end{equation*}

Así, concluimos que una combinación lineal que sirve es: $$(x^3+1)a(x)+(-x^6-x^3-x)b(x) = 1.$$

$\triangle$

Más adelante…

Como mencionamos, los conceptos que desarrollamos en esta sección son muy similares a los que desarrollamos para $\mathbb{Z}$, sin embargo, para que puedas acostumbrarte a la notación, en la siguiente entrada practicaremos como calcular el Máximo Común Divisor para dos polinomios.

Después de eso, el siguiente paso será extrapolar el concepto de elementos primos en el conjunto de los polinomios y con esa nueva herramienta ver la posibilidad de poder dar un resultado análogo al teorema fundamental de la aritmética que dimos en $\mathbb{Z}$.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Verifica que el conjunto $$f\mathbb{R}[x]+g\mathbb{R}[x]=\{rf+sg: r,s \in \mathbb{R}[x]\}$$ satisface las propiedades (1), (2) y (3) de la definición de ideal.
  2. Encuentra el máximo común divisor de los polinomios $x^8-1$ y $x^6-1$. Exprésalo como combinación lineal de ellos.
  3. Muestra que la intersección de dos ideales de $\mathbb{R}[x]$ es un ideal de $\mathbb{R}[x]$.
  4. Al único polinomio mónico $m$ tal que $$f\mathbb{R}[x]\cap g\mathbb{R}[x]=m\mathbb{R}[x]$$ le llamamos el mínimo común múltiplo de $f$ y $g$, y lo denotamos $\mcm{f,g}$. Muestra que es un múltiplo de $f$ y de $g$ y que es «mínimo» en el sentido de divisibilidad.
  5. Muestra que si $f$ y $g$ son polinomios mónicos en $\mathbb{R}[x]$ distintos del polinomio cero, entonces $fg = \MCD{f,g} \mcm{f,g}$. ¿Es necesaria la hipótesis de que sean mónicos? ¿La puedes cambiar por una hipótesis más débil?

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Seminario de Resolución de Problemas: Primos y factorización única

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En entradas anteriores hablamos de divisibilidad y de aritmética modular. Ahora platicaremos de las bloques que nos ayudan a construir a todos los enteros de manera multiplicativa: los números primos. Lo que dice el teorema fundamental de la aritmética es que todo número es producto de primos «de manera única». Tanto la teoría de números primos, como este teorema, son de gran ayuda en la resolución de problemas.

Como en entradas anteriores, el enfoque no es demostrar los resultados principales de la teoría. Esto se hace en un curso de Álgebra Superior II o en uno de Teoría de Números. La idea de la entrada es ver aplicaciones de estos resultados en situaciones concretas.

Números primos

Un entero es primo si tiene exactamente dos divisores positivos. El $1$ no es primo pues su único divisor es él mismo. Pero $2$, $17$ y $31$ sí son primos. De aquí y el algoritmo de la división, si $p$ es primo y $a$ es un entero, entonces $p\mid a$ o $\MCD{p,a}=1$.

Proposición 1. Si $p$ es un número primo que divide al producto de enteros $ab$, entonces $p\mid a$ ó $p\mid b$.

Demostración. Si $p$ no divide a $a$, entonces $\MDC(p,a)=1$, así que existe una combinación lineal entera $pn+am=1$. Multiplicando esta combinación por $b$, tenemos que $pbn+abm=b$. Como $p$ divide a $pbn$ y a $ab$, entonces divide a $b$.

$\square$

Problema. Muestra que si $p$ es un primo que divide a $123456^{654321}$, entonces $p$ divide a $123456$.

Sugerencia pre-solución. Aquí $123456$ y $654321$ no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.

Solución. Sea $a$ un entero, $n$ un entero positivo y $p$ un primo. Vamos a mostrar por inducción en $n$ que si $p\mid a^n$, entonces $p\mid a$. Para $n=1$ la conclusión es inmediata. Supongamos el resultado cierto para $n$. Si $p\mid a^{n+1}$, por la Proposición 1 tenemos que $p\mid a$ (en cuyo caso terminamos), o que $p\mid a^n$ (en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando $a=123456$ y $n=6543321$.

$\square$

Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.

Proposición 2. Si $p$ es primo, $a$ un entero y $n$ un entero positivo tales que $p\mid a^n$, entonces $p^n\mid a^n$.

Teorema fundamental de la aritmética

Todo número es producto de primos de manera única. Más específicamente

Teorema (teorema fundamental de la aritmética). Sean $a$ un entero positivo. Entonces existe un único $n$, únicos primos $p_1<\ldots<p_n$ y exponentes $\alpha_1,\ldots,\alpha_n$ tales que $$a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}.$$

La idea de la demostración es factorizar y factorizar. Si $n$ está expresado como producto de primos, ya está. Si no, hay uno de sus factores que no es primo y entonces se puede factorizar en dos números menores. Para probar la unicidad se usa la Proposición 1.

Veamos algunas aplicaciones del teorema fundamental de la aritmética.

Problema. Muestra que $\sqrt[3]{7}$ es un número irracional.

Sugerencia pre-solución. Procede por contradicción suponiendo que es racional para igualarlo a una fracción y eleva al cubo.

Solución. Si no fuera irracional, lo podríamos expresar como una fracción, digamos $\sqrt[3]{7}=\frac{a}{b}$ con $a$ y $b$ enteros. De aquí, $7b^3=a^3$. En la factorización en primos de $a^3$ y $b^3$ tenemos una cantidad múltiplo de $3$ de factores $7$. Así, en el lado derecho tenemos una cantidad mútiplo de $3$ de factores $7$ (por la Proposición 2), pero en el lado izquierdo no. Esto es una contradicción a la unicidad de la factorización en primos.

$\square$

Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.

Problema. Determina todos los enteros positivos $n$ para los cuales $2^8+2^{11}+2^n$ es un número entero al cuadrado.

Sugerencia pre-solución. Trabaja hacia atrás y usa notación adecuada. Intenta encontrar una diferencia de cuadrados.

Solución. Vamos a comenzar suponiendo $m^2=2^8+2^{11}+2^n$. De aquí, \begin{align*}
2^n&=m^2-2^8(1+2^3)\\
&=m^2-(3\cdot 2^4)^2\\
& =(m+48)(m-48).
\end{align*}

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números $m+48$ y $m-48$ tienen que ser potencias de $2$, digamos $m+48=2^a$ y $m-48=2^b$ con $a>b$ y $a+b=n$. Además tenemos que $$2^b(2^{a-b}-1)=96=2^5\cdot 3.$$

Como $2^{a-b}-1$ es impar, de nuevo por la unicidad de la factorización en primos debemos tener que $2^{a-b}-1=3$, y por lo tanto que $2^b=2^5$. De aquí, $b=5$ y $a-b=2$, y así $a=7$. Por lo tanto, el único candidato es $n=5+7=12$.

Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que $n$ en efecto es solución. Hacemos esto último notando que $2^8+2^{11}+2^{12}=2^8(1+2^3+2^4)=2^8\cdot 5^2$ que en efecto es un número cuadrado.

$\square$

Fórmulas que usan el teorema fundamental de la aritmética

Sean $a$ y $b$ números enteros positivos y $P={p_1,\ldots,p_n}$ el conjunto de números primos que dividen a alguno de $a$ o $b$. Por el teorema fundamental de la aritmética, existen exponentes $\alpha_1,\ldots,\alpha_n$ y $\beta_1,\ldots,\beta_n$, tal vez algunos de ellos cero, tales que \begin{align*}
a&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}\\ b&=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_n^{\beta_n}. \end{align*}

Por ejemplo, si $a=21, b=28$, entonces $P={2,3,7}$, $a=2^0 3^1 7^1$ y $b=2^2 3^0 7^1$.

Proposición 3. Se tiene que $a$ divide a $b$ si y sólo si para todo primo $p_i$ se tiene que $\alpha_i\leq \beta_i$.

Problema. ¿Cuántos múltiplos de $108$ hay que sean divisores de $648$?

Sugerencia pre-solución. Factoriza en primos a $108$ y a $648$ y usa la Proposición 3.

Solución. Tenemos que $108=2^23^3$ y que $648=2^3\cdot 3^4$. Por la Proposición 3, un número que funcione debe ser de la forma $2^a3^b$ con $2\leq a \leq 3$ y con $3\leq b \leq 4$. Así, $a$ tiene $2$ posibilidades y $b$ también, de modo que hay $2\cdot 2=4$ números que cumplen.

$\square$

Una consecuencia inmediata de la Proposición 3 anterior es la fórmula para el número de divisores de un entero en términos de los exponentes de su factorización en primos.

Proposición 4. El entero $a$ tiene $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)$ divisores positivos.

Problema. Determina cuántos enteros hay entre $1$ y $10000$ que tienen $49$ divisores positivos.

Sugerencia pre-solución. Usa la fórmula de la Proposición 4 para trabajar hacia atrás y ver qué forma debe tener un entero que cumple lo que se quiere. Divide en casos para que el producto se $49$.

Solución. Tomemos $a$ un entero y $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ su factorización en primos. Por la Proposición 4, necesitamos que $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)=49$.

A la izquierda tenemos puros números mayores o iguales que $2$. El número $49$ tiene como únicos divisores a $1$, $7$ y $49$. De esta forma, sólo hay dos casos posibles:

  • El número $a$ tiene sólo un divisor primo y $a=p_1^{48}$.
  • El número $a$ tiene dos divisores primos y $a=p_1^6p_2^6$.

El primer caso es imposible, pues $p_1$ sería por lo menos $2$ y $$2^{48}>2^{20}=(1024)^2>(1000)^2>10000.$$ Para el segundo caso, recordemos que $p_2>p_1$ en la factorización en primos. Si $p_2\geq 5$, entonces como $p_1\geq 2$, tendríamos $$a\geq (2\cdot 5)^6 = 1000000>10000,$$ así que esto no es posible.

La única otra posibilidad es $p_2=3$ y por lo tanto $p_1=2$. En este caso obtenemos al número $a=(2\cdot 3)^6=6^6=46656$, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.

$\square$

La factorización en primos también sirve para encontrar máximos comunes divisores y mínimos comunes múltiplos.

Proposición 4.  Se pueden calcular $\MCD{a,b}$ y $\mcm{a,b}$ como sigue:
\begin{align*}
\text{MCD}(a,b)&=p_1^{\min(\alpha_1,\beta_1)}\cdot p_2^{\min(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\min(\alpha_n,\beta_n)}\\
\text{mcm}(a,b)&=p_1^{\max(\alpha_1,\beta_1)}\cdot p_2^{\max(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\max(\alpha_n,\beta_n)}.
\end{align*}

Volvamos a ver un problema que ya habíamos resuelto con anterioridad.

Problema. Demuestra que $\MCD{a,b}\mcm{a,b}=ab$.

Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.

Solución. Expresemos a $a$ y $b$ en su factorización en primos como lo discutimos arriba. Al multiplicar $\MCD{a,b}$ y $\mcm{a,b}$, el exponente de $p_i$ es $\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i+\beta_i$. Este es el mismo exponente de $p_i$ en $ab$. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.3 del libro Problem Solving through Problems de Loren Larson.

Si $p$ es primo, entonces todo entero $n$ que no sea múltiplo de $p$ tiene inverso módulo $n$. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.