Archivo de la etiqueta: mínimo común múltiplo

Á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 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.

Álgebra Superior II: Teorema chino del residuo

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. También, aprendimos a resolver una ecuación lineal módulo $n$. El resultado principal fue el siguiente:

Teorema 1. Sean $a,b$ enteros y $n$ un entero positivo. La ecuación $ax\equiv b\pmod n$ tiene solución si y sólo si $M:=\text{MCD}(a,n)$ divide a $b$. Cuando sí hay solución, ésta se puede expresar de manera única en módulo $n’:=n/M$.

Ya que sabemos resolver una ecuación lineal, el siguiente paso es aprender a resolver sistemas que involucren dos o más ecuaciones lineales. En esta entrada veremos primero cómo resolver un sistema de dos ecuaciones lineales.

Luego, veremos cómo resolver un sistema con más ecuaciones y demostraremos un resultado clásico: el teorema chino del residuo. Pero para eso necesitaremos el resultado para dos ecuaciones lineales. Vamos poco a poco.

Sistemas de dos ecuaciones lineales

Supongamos que queremos entender por completo el sistema de ecuaciones
\begin{align*}
ax&\equiv b \pmod m\\
cx&\equiv d \pmod n,
\end{align*}

es decir, determinar cuándo existe una $x$ que satisfaga ambas ecuaciones y, si existe, determinar cómo se ven todas las soluciones. Por lo primero que nos tenemos que preocupar es por que cada una de las ecuaciones tenga solución: si alguna no tiene, entonces no hay solución para el sistema.

Así, lo primero que tiene que pasar es que $\text{MCD}(a,m)$ divida a $b$ y que $\text{MCD}(c,n)$ divida a $d$. Cuando sí tienen solución, entonces podemos intercambiar a las ecuaciones por sus ecuaciones reducidas y obtener el sistema de ecuaciones lineales equivalente
\begin{align*}
a’x&\equiv b’ \pmod {m’}\\
c’x&\equiv d’ \pmod {n’}.
\end{align*}

La primera ecuación tiene una única solución módulo $m’$ y la segunda una única solución módulo $n’$, así que este sistema es equivalente al sistema
\begin{align*}
x&\equiv e \pmod {m’}\\
x&\equiv f \pmod {n’},
\end{align*}

en donde $e$ y $f$ son las soluciones a cada una de las ecuaciones lineales reducidas por separado. Ahora sí podemos combinar ambas ecuaciones. Lo único que nos falta es entender cuándo los sistemas de esta forma tienen solución.

Ejemplo 1. El sistema lineal de ecuaciones
\begin{align*}
x&\equiv 2 \pmod 6\\
x&\equiv 4 \pmod {15}
\end{align*}
no tiene solución.

Solución. La primera ecuación implica que $6\mid x-2$. Como $3\mid 6$, por transitividad tenemos $3\mid x-2$, así que la primera ecuación implica que $x$ deja residuo $2$ al dividirse entre $3$.

La segunda ecuación implica que $15\mid x-4$. Como $3\mid 15$, por transitividad $3\mid x-4$, o bien $x\equiv 4 \equiv 1 \pmod 3$. Es decir, la segunda ecuación implica que $x$ deja residuo $1$ al dividirse entre $3$. De esta forma, es imposible satisfacer simultáneamente ambas ecuaciones.

$\triangle$

En el ejemplo anterior, $3$ es el máximo común divisor de $6$ y $15$ y por eso convino estudiar la divisibilidad entre $3$. La siguiente proposición justo dice cuándo el sistema tiene solución en términos de cierta divisibilidad por el máximo común divisor de los módulos.

Proposición 4. Sean $a$ y $b$ enteros y $m$ y $n$ enteros positivos. El sistema lineal de ecuaciones en congruencias
\begin{align*}
x&\equiv a \pmod m\\
x&\equiv b \pmod n
\end{align*}

tiene solución si y sólo si $M:=\text{MCD}(m,n)$ divide a $a-b$. En este caso, la solución se puede expresar de manera única módulo $N:=\text{mcm}(m,n)$, el mínimo común múltiplo de $m$ y $n$.

Demostración. Supongamos que $x$ es solución. Por la primera ecuación, $m\mid x-a$ y como $M\mid m$, entonces $M\mid x-a$. De manera análoga, $M\mid x-b$. Así, $M\mid (x-b)-(x-a)=a-b$, lo cual prueba una implicación de la proposición.

Por otro lado, si $M$ divide a $a-b$, entonces existe una combinación lineal de $m$ y $n$ que da $a-b$, digamos $ym+zn=a-b$, que podemos reescribir como $b+zn=a-ym$. Tomemos $x=b+zn=a-ym$. Notemos que
\begin{align*}
x&=a-ym\equiv a\pmod m\\
x&= b+zn \equiv b \pmod n,
\end{align*}

de modo que $x$ es solución para el sistema. Notemos que $x+rN$ para cualquier $r$ entero y $N$ el mínimo común múltiplo de $m$ y $n$ también es solución pues $N\equiv 0 \pmod m$ y $N\equiv 0 \pmod n$.

Veamos que la solución es única módulo $N$. Si tenemos $x$ y $y$ que son soluciones al sistema, entonces tenemos
\begin{align*}
x&\equiv a \equiv y\pmod m\\
x&\equiv b \equiv y\pmod n,
\end{align*}

lo cual implica $m\mid x-y$ y $n\mid x-y$. Como $N$ es el mínimo común múltiplo, $N\mid x-y$, de modo que $x\equiv y \pmod N$.

$\square$

Terminamos esta sección con un teorema que recopila todo lo que hemos mostrado para dos ecuaciones lineales.

Teorema 2. Consideremos el sistema de ecuaciones
\begin{align*}
ax&\equiv b \pmod m\\
cx&\equiv d \pmod n.
\end{align*}

Si $\text{MCD}(a,m)$ no divide a $b$ o $\text{MCD}(c,n)$ no divide a $d$, entonces el sistema no tiene solución. Si tenemos ambas divisibilidades, entonces el sistema original es equivalente al sistema
\begin{align*}
x&\equiv e \pmod {m’}\\
x&\equiv f \pmod {n’},
\end{align*}

donde $e$ y $f$ son las soluciones únicas a las reducciones de la primer y segunda congruencia respectivamente. Si $\text{MCD}(m’,n’)$ no divide a $e-f$, entonces el sistema original no tiene solución. Si sí, entonces el sistema original tiene una única solución módulo $\text{mcm}(m’,n’)$.

Ejemplo 2. Determina las soluciones al siguiente sistema lineal de ecuaciones:
\begin{align*}
4x&\equiv 12 \pmod {24}\\
10x&\equiv 5 \pmod {75}.
\end{align*}

Solución. Para la primera ecuación, notamos que $\text{MCD}(4,24)=4$ sí divide a $12$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x\equiv 3\pmod 6$.

Para la segunda ecuación, notamos que $\text{MCD}(10,75)=5$ sí divide a $5$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $2x\equiv 1\pmod {15}$. La solución de esta ecuación es $x\equiv 8 \pmod {15}$. De este modo, el sistema original es equivalente al sistema:

\begin{align*}
x&\equiv 3 \pmod {6}\\
x&\equiv 8 \pmod {15}.
\end{align*}

Tenemos que $\text{MCD}(6,15)=3$. Pero $3$ no divide a $3-8=-5$. Entonces este sistema no tiene solución, y por lo tanto el original tampoco.

$\triangle$

Hagamos un ligero cambio en el sistema de ecuaciones.

Ejemplo 3. Determina las soluciones al siguiente sistema lineal de ecuaciones:
\begin{align*}
4x&\equiv 20 \pmod {24}\\
10x&\equiv 5 \pmod {75}.
\end{align*}

Solución. Para la primera ecuación, notamos que $\text{MCD}(4,24)=4$ sí divide a $20$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x\equiv 5\pmod 6$.

Para la segunda ecuación, notamos que $\text{MCD}(10,75)=5$ sí divide a $5$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $2x\equiv 1\pmod {15}$. La solución de esta ecuación es $x\equiv 8 \pmod {15}$. De este modo, el sistema original es equivalente al sistema:
\begin{align*}
x&\equiv 5 \pmod {6}\\
x&\equiv 8 \pmod {15}.
\end{align*}

Tenemos que $\text{MCD}(6,15)=3$ y que $3$ sí divide a $5-8=-3$, de modo que sí hay solución. Para encontrarla, expresamos a $-3$ como combinación lineal de $6$ y $15$: $$5-8= -3 = (-3)\cdot 6 + 1\cdot 15.$$

De aquí, $x=8+15=23$ es una solución, y por lo tanto el conjunto de soluciones queda descrito módulo $\text{mcm}(6,15)=30$ de manera única como $$x\equiv 23 \pmod {30}$$.

$\triangle$

El teorema chino del residuo

Varias de las ideas que usamos para un sistema de dos ecuaciones lineales las podemos reciclar para cuando queremos encontrar una $x$ que satisfaga simultáneamente el sistema de ecuaciones lineales en congruencias
\begin{align*}
a_1x&\equiv b_1\pmod {m_1}\\
a_2x&\equiv b_2\pmod {m_2}\\
&\vdots\\
a_nx&\equiv b_n\pmod {m_n}
\end{align*}

Si este sistema tiene solución, entonces claramente:

  • Cada una de las ecuaciones debe tener solución y,
  • cada par de ellas debe tener solución.

Lo impresionante del siguiente teorema es que estas dos condiciones son las únicas que tenemos que verificar para que el sistema tenga solución. Y afortunadamente ya estudiamos cuándo dos ecuaciones lineales en congruencias tienen una solución simultánea.

Si cada una de las ecuaciones del sistema tiene solución, entonces es única, así que podemos remplazar cada ecuación por su solución y obtener un sistema de ecuaciones en donde todos los coeficientes de $x$ son $1$ (como le hicimos en el caso de dos ecuaciones). El siguiente resultado estudia estos sistemas.

Teorema 3. Sea $n\geq 2$ un entero, $b_i$ enteros para $i\in \{1,\ldots,n\}$ y $m_i$ enteros positivos para $i\in \{1,\ldots,n\}$. El sistema de ecuaciones en congruencias
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}
\end{align*}
tiene solución si y sólo si para cada par de índices $i$ y $j$ en $\{1,2,\ldots,n\}$ se tiene que la ecuación $i$ y la ecuación $j$ tienen solución, es decir, si y sólo si $\text{MCD}(m_i,m_j)\mid b_i-b_j$. En este caso, la solución es única módulo $\text{mcd}(m_1,\ldots,m_n)$.

Demostración. Si el sistema completo tiene solución, entonces claramente cualquier par de ecuaciones tiene solución. Para demostrar la afirmación inversa, procederemos por inducción. Para $n=2$ la afirmación es directa, pues justo la hipótesis es que ese par de ecuaciones tiene solución.

Supongamos entonces el resultado cierto para cuando tenemos $n$ ecuaciones y consideremos un sistema con $n+1$ ecuaciones
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}\\
x&\equiv b_{n+1}\pmod {m_{n+1}}.
\end{align*}

Supongamos que cualquier par de ellas tienen solución. Tenemos que mostrar que todo el sistema tiene solución y que es única módulo $\text{mcm}(m_1,\ldots,m_{n+1})$. Como cualquier par tienen solución, entonces cualquier par de las primeras $n$ tienen solución. Por hipótesis inductiva, entonces podemos reemplazar a las primeras ecuaciones por una ecuación módulo $N=\text{mcm}(m_1,\ldots,m_{n})$, que es única por la unicidad en la hipótesis inductiva. En otras palabras, existe un entero $c$ tal que el sistema de ecuaciones original es equivalente al sistema de ecuaciones
\begin{align*}
x&\equiv c \pmod N\\
x&\equiv b_{n+1} \pmod {m_{n+1}}
\end{align*}

Mostraremos ahora que este sistema tiene solución. Para esto, basta mostrar que $\text{MCD}(N,m_{n+1})$ divide a $c-b_{n+1}$.

Como $c$ es solución del sistema para las primeras $n$ ecuaciones, tenemos que $c\equiv b_i\pmod {m_i}$ para toda $i=1,\ldots, n$, es decir, $m_i\mid c-b_i$. Por transitividad, $\text{MCD}(m_{n+1},m_i)\mid c-b_i$.

Como cualquier par de ecuaciones de las originales tenía solución, tenemos que $\text{MCD}(m_{n+1},m_i)\mid b_i-b_{n+1}$. De esta forma, $$\text{MCD}(m_{n+1},m_i)\mid -(c-b_i)-(b_i-b_{n+1})=b_{n+1}-c.$$

Con esto mostramos que cada $\text{MCD}(m_{n+1},m_i)$ divide a $b_{n+1}-c$, de modo que el mínimo común múltiplo de estos números también divide a $b_{n+1}-c$. Pero el mínimo común múltiplo de estos números precisamente $\text{MCD}(N,m_{n+1})$.

En otras palabras, el sistema
\begin{align*}
x&\equiv c \pmod N\\
x&\equiv b_{n+1} \pmod {m_{n+1}},
\end{align*}

que es esquivalente al original, tiene una solución, y esta es única módulo $$\text{mcm}(N,m_{n+1})=\text{mcm}(m_1,\ldots,m_n,m_{n+1}).$$

Esto es justo lo que queríamos para dar el paso inductivo.

$\square$

Como corolario, obtenemos el teorema chino del residuo, que habla acerca de soluciones a sistemas de ecuaciones en los cuales los módulos que tomamos son primos relativos entre sí.

Teorema 4 (teorema chino del residuo). Sea $n\geq 2$ un entero, $b_i$ enteros para $i\in\{1,2,\ldots,n\}$ y $m_i$ enteros positivos para $i\in\{1,\ldots,n\}$. Supongamos además que cada par $m_i, m_j$ de enteros ($i\neq j$) son primos relativos. Entonces el sistema lineal de congruencias
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}
\end{align*}
tiene una y sólo una solución módulo $m_1m_2\ldots m_n$.

Demostración. Como cada pareja de módulos son primos relativos, tenemos que $\text{MCD}(m_i,m_j)=1$ y entonces claramente cada par de ecuaciones tiene solución. Por el Teorema 3, el sistema tiene solución y esta es única módulo el mínimo común múltiplo de $m_1,\ldots,m_n$, que como son primos relativos dos a dos, es $m_1m_2\ldots m_n$.

$\square$

La demostración del Teorema 3 también nos da un procedimiento para resolver de manera práctica los sistemas de ecuaciones lineales en congruencias:

  • Si los coeficientes de $x$ del sistema no son $1$, entonces primero resolvemos todas las ecuaciones con coeficiente distinto de $1$ para transformarla en una del estilo de las del Teorema 3. Si alguna no se puede, entonces el sistema no tiene solución.
  • Una vez que el sistema está en la forma del Teorema 3, verificamos si cada par de ecuaciones tienen solución calculando los máximos comunes divisores de dos en dos y viendo que dividen a las restas respectivas. Si alguno de estos pares falla, entonces el sistema no tiene solución.
  • Si todos los pares cumplen la hipótesis, entonces resolvemos las primeras dos ecuaciones para remplazarlas por otra módulo su mínimo común múltiplo. Luego, usamos esa que obtuvimos y la tercera para remplazarlas por otra. Seguimos así hasta que sólo nos queden dos ecuaciones. La solución a esas será la solución al sistema original.

Ejemplo. Resolvamos el siguiente sistema de congruencias:

\begin{align*}
x&\equiv 11 \pmod{5}\\
x&\equiv 5 \pmod{7}\\
x&\equiv 7 \pmod{11}
\end{align*}

Solución. Los números $5$, $7$ y $11$ son primos relativos por parejas, de modo que la solución existe y es única módulo $5\cdot 7 \cdot 11= 385$. Para encontrarla, primero resolvemos las primeras dos ecuaciones. Estas corresponden al sistema
\begin{align*}
x&\equiv 11\equiv 1 \pmod{5}\\
x&\equiv 5 \pmod{7}
\end{align*}

Para encontrar la solución, ponemos a $1-5=-4$ como combinación lineal de $5$ y $7$, que tras explorar un poco, se puede hacer así: $1-5=-4=2\cdot 5 + (-2)\cdot 7$. De este modo, la solución es $x\equiv 5-14 \equiv -9 \equiv 26 \pmod{35}$ (este es un buen momento para substituir en las dos ecuaciones originales y ver que todo vaya bien).

Así, el sistema original es equivalente al sistema
\begin{align*}
x&\equiv 26 \pmod{35}\\
x&\equiv 7 \pmod{11}
\end{align*}

Ahora lo que tenemos que hacer es expresar a $26-7=19$ como combinación lineal de $35$ y $11$. Es difícil encontrar una combinación «al tanteo», así que aquí es mejor usar el algoritmo de la división de Euclides:
\begin{align*}
35&=3\cdot 11 + 2\\
11&=2\cdot 5 + 1
\end{align*}

De aquí, $$1=11-2\cdot 5=11-(35-3\cdot 11)\cdot 5 = (-5)\cdot 35 +
16\cdot 11,$$ por lo que $$19=(-5\cdot 19)\cdot 35 + (19\cdot 16)\cdot 11=(-95)\cdot 35 + (304)\cdot 11.$$

Así, la solución al sistema está dada por $x=7+304\cdot 11=3351\equiv 271 \pmod {385}$.

$\square$

Más adelante…

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, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 2 sí son soluciones de la ecuación original.
  2. Cuando un sistema de dos ecuaciones en módulos $m$ y $n$ sí tiene solución, ¿cuántas soluciones módulo $mn$ tiene?
  3. Usando $(\ldots)$ para máximo común divisor y $[\ldots]$ para mínimo común múltiplo, demuestra que para cualesquiera enteros $m_1,m_2,\ldots,m_n$ se tiene que $$([m_1,\ldots,m_n],m_{n+1})=[(m_1,m_{n+1}),\ldots,(m_n,m_{n+1})].$$
  4. Verifica que las soluciones del último ejemplo en efecto satisfacen el sistema de ecuaciones inicial.
  5. Demuestra que para cualquier entero $n\geq 1$ existen $n$ enteros consecutivos tal que la factorización en primos de cada uno de ellos usa al menos dos primos diferentes.

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: Máximo común divisor

Por Leonardo Ignacio Martínez Sandoval

5 respuestas

Con esta entrada comenzamos a tratar los temas de números enteros y su aritmética. Varios de los temas que se ven aquí se estudian a profundidad en un curso de Álgebra Superior, así que varios de los resultados los enunciaremos sin demostración. Lo que nos interesa es cómo se pueden utilizar los resultados principales de la teoría de números enteros para la resolución de problemas matemáticos.

Divisibilidad y máximo común divisor

Trabajaremos todo el tiempo con números enteros, a menos que digamos lo contrario.

Decimos que $a$ divide a $b$ si $b$ es un mútiplo de $a$, es decir, si existe un $r$ tal que $b=ra$. Lo escribimos en símbolos como $a\mid b$. También decimos que $a$ es divisor de $b$.

Proposición 1. La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica. Si $a\mid b$ y $b\mid a$, entonces $|a|=|b|$, es decir $a=b$ o $a=-b$.

Si tenemos varios números $a_1,\ldots,a_n$, el máximo común divisor es el mayor número que divide a todos. El mínimo común múltiplo es el menor entero positivo que es múltiplo de todos. Los denotamos respectivamente por $\MCD{a_1,\ldots,a_n}$ y $\mcm{a_1,\ldots,a_n}$.

Proposición 2. Si $n$ divide a $a$ y a $b$, entonces divide a cualquier combinación lineal entera $ra+sb$ de ellos. En particular, si $n$ divide a dos términos de la igualdad $a+b=c$, entonces divide al tercero.

Notemos que $a+(b-a)=b$. Por la Proposición 2, un divisor de $a$ y $b$ será divisor de $b-a$, y uno de $b-a$ y de $a$ será divisor de $b$. De aquí sale que $\MCD{a,b}=\MCD{a,b-a}$

Problema. Determina todas las funciones $f:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{Z}^+$ tales que cumplen las siguientes tres propiedades simultáneamente:

  1. $f(a,a)=a$ para todo entero positivo $a$.
  2. $f(a,b)=f(b,a)$ para todo par de enteros positivos $a$ y $b$.
  3. $f(a,b)=f(a,a+b)$ para todo par de enteros positivos $a$ y $b$.

Sugerencia pre-solución. Haz casos particulares que puedas obtener a partir de esas propiedades para conjeturar el valor de $f(a,b)$ para todos $a$ y $b$ enteros positivos. Intenta probar tu conjetura por inducción fuerte.

Solución. Vamos a mostrar que $f(a,b)=\MCD{a,b}$ para todo par de enteros positivos $a$ y $b$. Vamos a probarlo por inducción sobre la suma $a+b$. Como $a$ y $b$ son enteros positivos, la menor suma que pueden tener es $2$ y en este caso $a+b=2$ implica $a=b=1$. Por la hipótesis 1, tenemos $f(1,1)=1$, que coincide con $\MCD{1,1}$.

Supongamos que el resultado es cierto cuando $a+b=k$ para todo entero $k=1,\ldots,n$ y tomemos $a$ y $b$ enteros de suma $n+1$. Si $a=b$, entonces $$f(a,b)=f(a,a)=a=\MCD{a,a}=\MCD{a,b},$$ como queremos. Si $a\neq b$, por la simetría que nos da la hipótesis 2 podemos suponer $b>a$. Por la hipótesis 3, $$f(a,b)=f(a,a+(b-a))=f(a,b-a).$$ En la expresión de la derecha, tenemos que sus entradas suman $a+(b-a)=b<a+b=n+1$, de modo que podemos aplicar la hipótesis inductiva para obtener que $f(a,b-a)=\MCD{a,b-a}$. Por la discusión antes de este problema, $\MCD{a,b-a}=\MCD{a,b}$. Así, concluimos que $f(a,b)=\MCD{a,b}$, como queríamos.

$\square$

El máximo común divisor y el mínimo común múltiplo de un número son especiales. No sólo son el divisor más grande y el múltiplo más chico, sino que además si hay otro divisor de todos los números (o múltiplo de todos los números), además se cumplen ciertas divisibilidades.

Proposición 3. Si tenemos otro número $d$ que sea divisor de $a_1,\ldots,a_n$, entonces $$d\mid \MCD{a_1,\ldots,a_n}.$$ Si tenemos otro número $M$ que sea múltiplo de $a_1,\ldots,a_n$, entonces $$\mcm{a_1,\ldots,a_n}\mid M.$$

Problema. Sean $a$ y $b$ enteros positivos. Muestra que $$\MCD{a,b}\mcm{a,b}=ab.$$

Sugerencia pre-solución: Intenta resolver el problema antes de ver la solución. Para ello, necesitarás la Proposición 1 y la Proposición 3.

Solución. Para simplificar la notación, tomamos $D=\MCD{a,b}$ y $m=\mcm{a,b}$.

Como $D$ divide a $a$ y $b$, existen enteros $r$ y $s$ tales que $a=rD$ y $b=sD$. Notemos que $rsD=as=br$, así que $rsD$ es un múltiplo de $a$ y $b$, y por la Proposición 3, tenemos que $m\mid rsD$. Multiplicando por $D$ esta divisibilidad, tenemos que $Dm\mid rsD^2=ab$.

Como $ab$ es múltiplo de $a$ y de $b$, por la Proposición $3$ es múltiplo de $m$, digamos $ab=km$. Notemos que de aquí, tenemos $a=k(m/b)$ con $m/b$ entero y $b=k(m/a)$ con $m/a$ entero, de modo que $k$ divide a $a$ y a $b$. Como $D$ es máximo común divisor, por la Proposición 3 tenemos que $k\mid D$. Multiplicando por $m$ esta divisibilidad, tenemos que $km\mid DM$, es decir, $ab\mid Dm$.

Con esto logramos conseguir que $ab\mid Dm$ y $Dm\mid ab$. Por la Proposición $1$, tenemos que $|ab|=|Dm|$, pero como $a$, $b$, $D$, $m$ son positivos, entonces $ab=Dm$.

$\square$

Algoritmo de la división y algoritmo de Euclides

Tomemos $a$ y $b$ enteros. Si intentamos expresar a $a$ como múltiplo de $b$, puede que no lo logremos. Pero podemos acercarnos lo más posible y dejar un residuo «pequeño». Esto es lo que dice el algoritmo de la división.

Teorema 1 (Algoritmo de la división). Para enteros $a$ y $b\neq 0$, existen únicos enteros $q$ y $r$ tales que $0\leq r < |b|$ y $a=bq+r$.

Consideremos la igualdad $a=bq+r$ en el algoritmo de la división y apliquemos la Proposición 2. Si $d$ divide a $a$ y $b$, entonces divide a $r$. Si $d$ divide a $r$ y a $b$, entonces divide a $a$. Así, $\MCD{a,b}=\MCD{b,r}$, en donde $b$ y $r$ ahora son números más chicos que $a$ y $b$. De este modo, podemos hacer varias veces el algoritmo de la división para obtener igualdades
\begin{align*}
a&=bq_1+r_1\\
b&=r_1 q_2 + r_2\\
r_1&= r_2q_3 + r_3\\
&\vdots\\
r_{n-2}&= r_{n-1}q_n + r_n\\
r_{n-1}&= r_nq_{n+1} + 0\\
\end{align*}

de las que obtenemos $$\MCD{a,b}=\MCD{b,r_1}=\ldots=\MCD{r_n,0}=r_n.$$
En las igualdades llegamos a un residuo $0$ pues $b>r_1>r_2>r_3>\ldots\geq 0$ es una sucesión estrictamente decreciente de enteros no negativos.

En particular, obtenemos $$\MCD{a,b}=r_n.$$ A esto se le conoce como el algoritmo de Euclides, que enunciamos en otras palabras a continuación.

Teorema 2 (Algoritmo de Euclides). Podemos obtener el máximo común divisor de $a$ y $b$ aplicando el algoritmo de la división a $a$ y $b$, a $b$ y el residuo obtenido y luego repetidamente a los residuos que se van obteniendo. El último residuo no cero es $\MCD{a,b}$.

Hay todavía una conclusión adicional muy importante que podemos obtener a partir del algoritmo de Euclides.

Problema. Sean $a\geq b$ enteros. Sean $q_i$ y los $r_i$ los números obtenidos en el algoritmo de Euclides. Definimos recursivamente una sucesión de $n+1$ vectores en $\mathbb{R}^3$ como sigue:

\begin{align*}
v_1&=(a,1,0)\\
v_2&=(b,0,2)\\
v_{i+2}&=v_{i}-q_iv_{i+1}\quad \text{para $i=1,\ldots,n-1$}
\end{align*}

Sean $r_{-1}=a$ y $r_{0}=b$. Muestra que para $i=1,2,3,\ldots,n+1$ se tiene que $v_i=(x_i,y_i,z_i)$, en donde:

  • $x_i=r_{i-2}$
  • $x_i=ay_i+bz_i$

Sugerencia pre-solución. Intenta resolver el problema haciendo inducción sobre el índice. Los casos $i=1,2$ son inmediatos.

Solución. Procedemos por inducción fuerte en el subíndice $i$. Para $i=1,2$, el resultado es cierto pues $x_1=a=r_{-1}$, $x_2=b=r_0$, $a=1\cdot a + 0 \cdot b$ y $b=0 \cdot a + 1\cdot b$. Supongamos el resultado cierto para los índices $1,2,\ldots, k$ para algún $2\leq k\leq n$. Tomemos el índice $k+1$.

Estudiemos primero la entrada $x_{k+1}$. Por definición de la recursión e hipótesis inductiva
\begin{align*}
x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\
&=r_{k-3}-q_{k-1}r_{k-2}\\
&=r_{k-1},
\end{align*}

que es lo que queríamos mostrar para la entrada $x_{k+1}$. Para la segunda parte, de nuevo usando la recursión e hipótesis inductiva, tenemos que
\begin{align*}
x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\
&=ay_{k-1}+bz_{k-1} – q_{k-1} (ay_{k}+bz_{k})\\
&=a(y_{k-1}-q_{k-1}y_k) + b(z_{k-1}-q_{k-1}z_k)\\
&=ay_{k+1}+bz_{k+1}.
\end{align*}

Con esto terminamos la inducción.

$\square$

El problema anterior nos dice que, en particular, $r_n=ay_n+bx_n$. Esta conclusión es muy importante y la enunciamos como teorema.

Teorema 3. El máximo común divisor de enteros $a$ y $b$ se puede escribir como combinación lineal entera de $a$ y $b$, es decir, existen enteros $m$ y $n$ tales que $\MCD{a,b}=am+bn$.

Veamos un ejemplo concreto de cómo podemos usar el problema para encontrar la combinación lineal que da el máximo común.

Problema. Expresa al máximo común divisor de $754$ y $221$ como combinación lineal entera de estos números.

Solución. Hacemos la siguiente tabla, en donde ponemos a los vectores del problema como vectores columna (en los renglones $2,3,4$). En el primer rengón vamos apuntando las $q_i$.

3223
7542219139130
101-25-17
01-37-1758

Explicamos un poco más de donde sale la tabla. Las primeras dos columnas son los vectores $v_1$ y $v_2$ del problema, que son $(754,1,0)$ y $(221,0,1)$. Para la tercer columna, nos preguntamos ¿cuántas veces cabe $221$ en $754$? La respuesta es $3$, así que ponemos un $3$ arriba (para acordarnos) y hacemos la resta de la primera columna menos tres veces la segunda. Eso va en la tercer columna.

Para la cuarta columna, nos preguntamos ¿cuántas veces cabe $91$ en $221$? La respuesta es $2$, así que lo apuntamos arriba, y la cuarta columna es la segunda, menos dos veces la tercera. Continuamos así hasta que obtengamos un $0$. La columna anterior nos dice que $13$ es el máximo común divisor, y que la combinación lineal es $$13=754\cdot 5 + 221 \cdot 58.$$

$\square$

Aquí hay otros dos problemas con aplicaciones de las ideas que vimos en esta entrada.

Problema. Muestra que para todo entero $n$ se tiene que la fracción $\frac{41-6n}{9n-61}$ es irreducible.

Sugerencia pre-solución. Intenta resolver el problema. Lo que quieres mostrar es que $41-6n$ y $9n-61$ nunca tienen divisores en común.

Solución. Notemos que $41-6n$ y $9n-61$ tienen una combinación lineal que da $1$. En efecto, $$3\cdot (41-6n) + 2\cdot (9n-61) = 123-18n+18n-122=1.$$

Cualquier entero $d$ que divida a $41-6n$ y a $9n-61$ tiene entonces que dividir a $1$, lo cual muestra que $\MCD{41-6n,9n-61}=1$, y por lo tanto la fracción siempre es irreducible.

$\square$

Problema. Se tiene un número irracional $\alpha$ para el cual $\alpha^{91}$ y $\alpha^{119}$ son números racionales. Muestra que $\alpha^{14}$ es un número racional.

Sugerencia pre-solución. Encuentra el máximo común divisor de $91$ y $119$. Recuerda que las potencias de racionales son racionales, y productos de racionales también.

Solución. Como $91=7\cdot 13$ y $119=7\cdot 13$, tenemos que $\MCD{91,119}=7$. De esta forma, existen enteros $m$ y $n$ tales que $7=91m+119n$, de donde $14=91 \cdot (2m)+119 \cdot(2n)$.

Sabemos que $\alpha^{91}$ es racional, así que $(\alpha^{91})^{2m}$ también. Análogamente, $(\alpha^{119})^{2n}$ es racional. De esta forma, el número $$\alpha^{14}=(\alpha^{91})^{2m}\cdot (\alpha^{119})^{2n}$$ también lo es.

$\square$

Más ejemplos

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

El Teorema 3 es fundamental para cuando se quieren determinar inversos multiplicativos trabajando módulo $n$.