Archivo de la etiqueta: aritmética

Seminario de Resolución de Problemas: Aritmética de números complejos

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En entradas anteriores de esta sección hablamos de propiedades aritméticas de números enteros. En esta entrada veremos varias de las propiedades aritméticas de los números complejos y cómo se pueden usar para resolver problemas, incluso aquellos en los que los números complejos no están mencionados de manera explícita en el enunciado.

Distintas formas de los números complejos

La forma más común en la que pensamos en números complejos es en su forma rectangular, en donde un complejo se escribe de la forma $z=a+bi$, en donde $a$ y $b$ son números reales y pensamos a $i$ como un número tal que $i^2=-1$. A $a$ le llamamos la parte real y a $b$ la parte imaginaria.

Podemos colocar al complejo $z=a+ib$ en el plano cartesiano, identificándolo con el punto $(a,b)$. De aquí, la forma polar del complejo es $z=r(\cos \theta + i \sin \theta)$, en donde $r$ es la norma $|z|:=\sqrt{a^2+b^2}$ y si $z\neq 0$, $\theta$ es el argumento, que es el ángulo en el sentido antihorario desde el origen entre el eje horizontal y el punto $(a,b)$. Si $z=0+i0=0$, no definimos el argumento.

Forma polar y rectangular de un complejo
Forma polar y rectangular de un complejo.

Así como le hacíamos en el caso de trabajar con módulos, a veces conviene pensar que el argumento es el único ángulo en $[0,2\pi)$ que cumple lo anterior. En otras ocasiones, conviene pensar al argumento como a veces que es la clase de todos los ángulos módulo $2\pi$.

Cuando tenemos a complejos $w=a+ib$ y $z=c+id$ en forma rectangular, su suma $w+z=(a+c) + i(b+d)$ corresponde geométricamente a encontrar la diagonal del paralelogramo definido por $(a,b)$, $(c,d)$ y el origen, pues corresponde justo al punto $(a+c,b+d)$.

Suma de números complejos
Suma de números complejos.

Su multiplicación $wz$ en forma rectangular es $(ac-bd)+(ad+bc)i$, que geométricamente no es tan claro que sea.

La forma exponencial $z=re^{i\theta}$ es simplemente una forma de abreviar a la forma polar, pues por definición $e^{i\theta}=\cos \theta + i \sin \theta$. En forma exponencial, el producto es más sencillo de entender.

Ejercicio. Demuestra lo siguiente:

  • Muestra que la norma es multiplicativa, es decir, que para complejos $r$ y $s$ se tiene que $|rs|=|r||s|$.
  • Muestra que $e^{i\alpha}e^{i\beta}=e^{i(\alpha+\beta)}$.

Sugerencia. Para el primer punto, haz las cuentas usando la forma rectangular. Para el segundo punto, escribe las definiciones de todos los términos en forma polar. Haz las multiplicaciones en el lado izquierdo y usa las fórmulas trigonométricas para sumas de ángulos.

Por el ejercicio anterior, si tenemos a los complejos en forma polar $w=re^{i\alpha}$, $z=se^{i\beta}$, entonces el producto es $wz=rse^{i(\alpha+\beta)}$, de modo que el producto corresponde al complejo con el producto de normas y suma de argumentos. En ocasiones esto nos permite plantear algunos problemas geométricos en términos de números complejos.

Producto de números complejos.
Multiplicación de números complejos.


Aplicaciones de aritmética de complejos

Veamos dos aplicaciones de la teoría anterior a problemas que no mencionan en el enunciado a los números complejos.

Problema. Sean $a$ y $b$ enteros. Muestra que el número $(a^2+b^2)^n$ se puede expresar como la suma de los cuadrados de dos números enteros.

Podría ser tentador usar el binomio de Newton para elevar el binomio a la $n$-ésima potencia. Sugerimos que intentes esto para darte cuenta de las dificultades que presenta.

Sugerencia pre-solución. Escribe a $a^2+b^2$ como el cuadrado de la norma de un complejo y usa que es multiplicativa.

Solución. El número $r=a^2+b^2$ es la norma al cuadrado del número complejo $z=a+ib$. Entonces, el número $r^n=(a^2+b^2)^n$ es la norma al cuadrado del número complejo $z^n=(a+ib)^n$. Pero al desarrollar $(a+ib)^n$ obtenemos únicamente a $i$, potencias de $a$ y de $b$, y coeficientes binomiales. De modo que $z^n=(a+ib)^n=c+id$ con $c$ y $d$ enteros (aquí estamos usando notación adecuada: no es necesario saber quienes son, sólo que son enteros). Así, $r^n=c^2+d^2$ con $c$ y $d$ enteros.

$\square$

Veamos ahora un ejemplo de geometría. Este problema es posible resolverlo de muchas formas, pero notemos que los números complejos nos dan una forma de hacerlo de manera algebraica de manera inmediata.

Problema. En la siguiente figura hay tres cuadrados de lado $1$ pegados uno tras otro. Determina la suma de los ángulos marcados con $\alpha$ y $\beta$.

Problema de suma de ángulos
Determinar el valor de la suma $\alpha+\beta$.

Sugerencia pre-solución. El problema pide determinar una suma de ángulos, así que conviene pensar esta suma de ángulos como el ángulo del producto de dos complejos. Haz tu propia figura, pero ahora sobre el plano complejo.

Solución. El ángulo $\alpha$ es igual al argumento del complejo $2+i$ y el ángulo $\beta$ es igual al argumento del complejo $3+i$. De esta forma, $\alpha+\beta$ es igual al argumento del complejo $(2+i)(3+i)=(6-1)+(2+3)i=5+5i$. Este complejo cae sobre la recta $\text{Re}(z)=\text{Im}(z)$, de modo que su argumento es $\pi / 4$.

$\square$

Este problema también se puede resolver de (numerosas) maneras geométricas, que puedes consultar en este video.

Fórmula de De Moivre

El siguiente teorema se puede demostrar por inducción sobre $n$.

Teorema (fórmula de De Moivre). Para cualquier entero $n$ y ángulo $\theta$ se tiene que $$(\cos \theta + i \sin \theta)^n=\cos (n\theta) + i \sin (n\theta).$$ Dicho de otra forma, en términos de la forma exponencial, se vale usar la siguiente ley de los exponentes $$(e^{\theta i})^n=e^{(n\theta) i}.$$

La fórmula de De Moivre es otra herramienta que ayuda a resolver problemas de números reales enunciándolos en términos trigonométricos. El truco consiste en:

  1. Tomar una expresión real que queramos entender.
  2. Identificarla como la parte real o imaginaria de una expresión compleja.
  3. Usar la aritmética de números complejos para entender la expresión compleja.
  4. Regresar lo que entendamos a los reales.

Veamos un par de ejemplos, relacionados con funciones trigonométricas. Comenzamos con una fórma de encontrar la fórmula para el coseno de cinco veces un ángulo.

Problema. Sea $\theta\in [0,2\pi)$. Expresa a $\cos 5\theta$ en términos de $\cos \theta$.

Sugerencia pre-solución. Identifica a $\cos 5\theta$ como la parte real de un número complejo. Inspírate en la fórmula de De Moivre. Usa binomio de Newton.

Solución. Por la fórmula de De Moivre, $\cos 5\theta$ es la parte real del complejo $(\cos \theta + i \sin \theta)^5$, así que calculemos quién es exactamente este número usando binomio de Newton. Para simplificar la notación, definimos $a=\cos \theta$ y $b=\sin \theta$. Tenemos que

\begin{align*}
(a+ib)^5&=a^5+5a^4(bi)+10a^3(ib)^2+10a^2(ib)^3+5a(ib)^4+(ib)^5\\
&=(a^5-10a^3b^2+5ab^4) + (5a^4b-10a^2b^3+b^5) i.
\end{align*}

Además, por la identidad pitagórica recordemos que $a^2+b^2=1$, de donde $b^2=1-a^2$, de modo que la parte real de la expresión anterior es $$a^5-10a^3(1-a^2)+5a(1-2a^2+a^4),$$ que agrupando es $$16a^5-20a^3+5a.$$ Recordando que $a$ es $\cos \theta$, obtenemos la fórmula final $$\cos 5\theta = 16\cos^5 \theta – 20 \cos^3 \theta + 5\cos \theta.$$

$\square$

Raíces de la unidad

En muchos problemas se utilizan las raíces de la ecuación $x^n=1$.

Teorema. Sea $n\geq 1$ un entero. Las ecuación $x^n=1$ tiene $n$ soluciones complejas, que en el plano complejo forman los vértices del $n$-ágono regular con centro en $0$ y tal que uno de sus vértices es $1$. Si $\omega$ es la raíz de menor argumento positivo, entonces estas soluciones son $1,\omega, \omega^2,\ldots,\omega^{n-1}$.

Raíces de la unidad en los números complejos
Raíces $n$-ésimas de la unidad para $n=5$.

A estas soluciones les llamamos las raíces $n$-ésimas de la unidad. Notemos que $\omega^{n}=1$, y que en general si escribimos a un entero $m$ usando el algoritmo de la división como $m=qn+r$, entonces $\omega^m=\omega^r$. ¡Los productos de raíces de la unidad se comportan como los elementos de $\mathbb{Z}_n$ bajo suma módulo $n$!

Proposición. Sea $n\geq 2$ un entero. La suma de las $n$ raíces $n$-ésimas de la unidad es $0$ y su producto es $1$.

La proposición anterior nos permite, en ocasiones, «filtrar» ciertas expresiones algebraicas. A continuación presentamos un ejemplo, que retomamos de los primeros ejemplos que vimos, cuando estábamos aprendiendo la heurística de encontrar un patrón.

Problema. Determina el valor de la suma $$\binom{100}{0}+\binom{100}{3}+\binom{100}{6}+\ldots+\binom{100}{99}.$$

Sugerencia pre-solución. Si no recuerdas lo que debería salir, vuelve a experimentar con los primeros valores, para cuando en vez de usar $100$ se usan números más chiquitos. Para entender mejor el patron, generaliza el problema, y en vez de sólo tener múltiplos de $3$ abajo, explora también qué sucede cuando tienes los números que dejan residuo $0$, $1$ o $2$ módulo $3$.

Ya que recuerdes la fórmula que queremos, considera una raíz cúbica $\omega$ de la unidad distinta de $1$. Calcula $(1+1)^{100}$, $(1+\omega)^{100}$ y $(1+\omega^2)^{100}$ usando el binomio de Newton y aprovechando que toda potencia de $\omega$ es $1$, $\omega$ u $\omega^2$ para simplificar la notación.

Solución. Sea $\omega$ una raíz cúbica de la unidad distinta de $1$. Tenemos que $\omega^3=1$ y que $1+\omega+\omega^2=0$. De este modo, podemos usar $\omega$ y el binomio de Newton para calcular las siguientes expresiones

\begin{align*}
(1+1)^{100}&=\binom{100}{0}+\binom{100}{1}+\binom{100}{2}+ \binom{100}{3}+ \ldots\\
(1+\omega)^{100}&= \binom{100}{0}+\binom{100}{1}\omega+\binom{100}{2}\omega^2+\binom{100}{3}+\ldots\\
(1+\omega^2)^{100}&= \binom{100}{0}+\binom{100}{1}\omega^2+\binom{100}{2}\omega+ \binom{100}{3}+\ldots
\end{align*}

¿Qué sucede al sumar las tres expresiones? En el lado derecho, cada vez que $m$ es un múltiplo de $3$, tenemos $3\binom{100}{m}$, y cada vez que $m$ no es un múltiplo de $3$, tenemos $$(1+\omega+\omega^2)\binom{100}{m}=0.$$ ¡Se filtran exactamente los coeficientes binomiales con parte inferior múltiplo de $3$! Así, tres veces la suma que buscamos es igual a $$2^{100}+(1+\omega)^{100}+(1+\omega^2)^{100}.$$

Esta ya es una expresión suficientemente cerrada, pero podemos simplificar todavía más:

\begin{align*}
(1+\omega)^{100}&=(-\omega^2)^{100}=\omega^{200}=\omega^2\\
(1+\omega^2)^{100}&=(-\omega)^{100}=\omega\\
(1+\omega)^{100}+(1+\omega^2)^{100}&=\omega^2+\omega=-1.
\end{align*}

Así, la expresión que queremos es $\frac{2^{100}-1}{3}$.

$\square$

Más ejemplos

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

Álgebra Superior II: Ecuaciones diofantinas

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores platicamos de congruencias y teoremas que nos sirven para trabajar con aritmética modular. Así mismo, aprendimos a resolver ecuaciones lineales y sistemas de ecuaciones lineales en congruencias en una variable.

Regresemos a $\mathbb{Z}$. Se usa el término ecuación diofantina para referirse a una ecuación en la cual las variables deben tomar soluciones enteras. Existe una gran variedad de formas que puede tomar una ecuación diofantina. «Resolver una ecuación diofantina» se refiere a encontrar, con demostración, una descripción del conjunto de todas sus soluciones en «términos sencillos».

Ejemplo 1. Encuentra todas las soluciones enteras $x$ a la ecuación $13x=91$.

Ejemplo 2. Encuentra todas las soluciones enteras $x,y$ a la ecuación $7x+5y=3$.

Los ejemplos $1$ y $2$ son ecuaciones diofantinas lineales en una y dos variables respectivamente. El objetivo de esta entrada es explicar cómo resolver estas ecuaciones. Continuamos la discusión de más ejemplos para abrir el panorama del tipo de problemas que aparecen en el área, y de las técnicas que se pueden usar.

Ejemplo 3. Encuentra todas las soluciones con enteros $x,y,z$ a la ecuación $x^2+y^2=z^2$.

Al Ejemplo 3 se le conoce como la ecuación pitagórica. Esa es posible resolverla con todo lo que hemos visto hasta ahora, pero no es tan sencillo. Requiere de un análisis cuidadoso de casos.

Ejemplo 4. Encuentra todas las soluciones enteras positivas $x,y$ a la igualdad $x^y=y^x$.

El Ejemplo $4$ es curioso. Si consideramos a la función real $f(x)=x^{\frac{1}{x}}$, el problema pide encontrar a aquellas parejas de enteros $x$ y $y$ tales que $f(x)=f(y)$. Una forma de resolver la ecuación es utilizando herramientas de cálculo diferencial en $f(x)$ para mostrar que para $x>5$ la función ya es estrictamente creciente. Esto reduce el análisis de casos de enteros que tenemos que intentar, y muestra que $(2,4)$, $(4,2)$ y $(n,n)$ son las únicas parejas de enteros válidas. La moraleja de este ejemplo es que a veces se tienen que usar herramientas de otras áreas de las matemáticas para resolver una ecuación, aunque esta sólo requiera de soluciones enteras.

Ejemplo 5. Encuentra todas las soluciones con enteros $x,y,z$ a la ecuación $x^3+y^3=z^3$.

El Ejemplo $5$, o bien cualquier ecuación del estilo $x^n+y^n=z^n$ se le llama una ecuación de tipo Fermat, pues Pierre Fermat conjeturó que no existen soluciones para cuando $n\geq 3$ y $x,y,z$ son todos distintos de cero. Esta conjetura fue demostrada en $1995$ por Andrew Wiles. Una demostración de esta conjetura queda muy lejos de la teoría que hemos desarrollado hasta ahora, pero vale la pena decir que esta ecuación motivó fuertemente el desarrollo de varias herramientas de teoría de números, sobre unas llamadas curvas elípticas.

Ejemplo 6. Encuentra todas las soluciones enteras positivas $x,y$ a la igualdad $|2^x-3^y|=1$.

El Ejemplo $6$ se puede resolver también con herramientas que ya hemos visto en el curso, pero requiere de un análisis detallado. Este problema pide, en otras palabras, determinar cuándo «una potencia de $3$ está junto a una potencia de $2$». Un ejemplo de esto son $2^3=8$ y $3^2=9$. Otra pregunta clásica del área es la conjetura de Catalán, la cual afirma que estas son las únicas dos potencias no triviales que son consecutivas. Fue demostrada en $2002$ por Mihăilescu. Las técnicas también están muy lejos del alcance de este curso. Se usan técnicas en campos ciclotómicos y módulos de Galois.

En realidad, uno podría tomar cualquier ecuación en reales y hacerse la pregunta de si existirán soluciones en enteros y, de ser así, determinar cuántas o cuáles son. Ha existido (y existe) mucha investigación en el área. El interés de una ecuación diofantina en particular está relacionado con su aplicación a otros problemas y con la teoría que ayuda a desarrollar.

Ecuaciones diofantinas lineales

La ecuación diofantina del Ejemplo 1 se puede preguntar en general. Dados enteros $a$ y $b$, ¿cuáles son las soluciones enteras $x$ a la ecuación $ax=b$?

  • Si $a=0$, la ecuación tiene solución si y sólo si $b=0$, y en este caso, cualquier valor entero de $x$ es solución.
  • Si $a\neq 0$, esta ecuación tiene solución en enteros si y sólo si $a$ divide a $b$, y en este caso $x=b/a$ es la única solución entera.

Estudiemos ahora la generalización del Ejemplo 2.

Problema. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero. Determina todas las soluciones enteras a la ecuación $$ax+by=c.$$

Primero, determinemos condiciones necesarias y suficientes en $a$, $b$ y $c$ para que la ecuación tenga soluciones enteras $x$ y $y$. Lo que nos está pidiendo la ecuación es que escribamos a $c$ como combinación lineal entera de $a$ y $b$. Recordemos que $$a\mathbb{Z}+b\mathbb{Z} = \text{MCD}(a,b) \mathbb{Z},$$ de modo que la ecuación tiene solución si y sólo si $\text{MCD}(a,b)$ divide a $c$. ¿Cuáles son todas las soluciones? Esto lo determinaremos mediante las siguientes proposiciones.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero divisible entre $M:=\text{MCD}(a,b)$. Sean $a’=a/M$, $b’=b/M$, $c’=c/M$. Las soluciones enteras a la ecuación $ax+by=c$ son las mismas que para la ecuación $a’x+b’y=c’$.

Demostración. Se sigue de manera directa usando que $M\neq 0$, ya que de la original podemos pasar a la nueva dividiendo entre $M$, y de la nueva a la anterior multiplicando por $M$.

$\square$

Ejemplo 1. $x=2$ y $y=7$ son soluciones a la ecuación $6x-4y=-16$, y también son soluciones a la ecuación $3x-2y=-8$.

$\triangle$

Al dividir ambos lados de la ecuación entre el máximo común divisor de $a$ y $b$ obtenemos una ecuación en la que los coeficientes de las variables ahora son primos relativos. Este fenómeno ya lo habíamos visto cuando hablamos de ecuaciones en congruencias. Estudiemos este tipo de ecuaciones en enteros. Comenzaremos con unas un poco más sencillas: aquellas en las que $c=0$. A estas les llamamos ecuaciones homogéneas.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y primos relativos. Las soluciones de la ecuación diofantina $ax+by=0$ son exactamente de la forma $x=-kb$, $y=ka$ para $k$ en los enteros.

Demostración. De la ecuación obtenemos $-ax=by$, por lo que $a$ divide a $by$. Como $a$ y $b$ son primos relativos, tenemos que $a$ divide a $y$. Así, existe un $k$ entero tal que $y=ka$. Entonces, $-ax=bka$. Como $a\neq 0$, podemos cancelar y despejar $x=-kb$.

En efecto, todas estas parejas son soluciones pues $a(-kb)+b(ka)=0$.

$\square$

Ejemplo 2. Determina todas las soluciones a la ecuación diofantina $9x+5y=0$.

Solución. Tenemos que $9$ y $5$ son primos relativos y que la ecuación es homogénea. Por el resultado anterior, las soluciones son de la forma $x=-5k$ y $y=9k$.

$\triangle$

Ejemplo 3. Determina todas las soluciones a la ecuación diofrantina $9x-6y=0$.

Solución. Aquí hay que tener cuidado. Si bien la ecuación es homogénea, los coeficientes de las variables no son primos relativos. Si sólo consideramos las soluciones de la forma $x=6k$ y $y=9k$, en efecto todas estas son soluciones, pero nos faltará la solución $x=2$, $y=3$ que no es de esta forma.

Antes de poder usar la proposición, necesitamos dividir entre el máximo común divisor de $9$ y $6$, que es $3$, para obtener primero la ecuación diofantina equivalente $3x-2y=0$. Ahora sí, todas las soluciones enteras de esta ecuación (y por lo tanto de la original) son de la forma $x=2k$ y $y=3k$.

$\triangle$

Pasemos ahora al caso en el que los coeficientes de las variables son primos relativos, pero la ecuación ya no es homogénea.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y primos relativos. Sea $c$ un entero divisible entre $\text{MCD}(a,b)$. Se puede obtener una solución $x_0, y_0$ a la ecuación diofantina $ax+by=c$ usando el algoritmo de Euclides. El resto de las soluciones son exactamente de la forma $x=x_0-kb$, $y=y_0+ka$ en donde $k$ es cualquier entero positivo.

Demostración. Notemos que en efecto las soluciones propuestas satisfacen la ecuación diofantina pues
\begin{align*}
ax+by&=a(x_0-kb)+b(y_0+ka)\\
&=ax_0+by_0 + (-kab+kab)\\
&=ax_0+by_0\\
&=c.
\end{align*}

Aquí usamos que $x_0,y_0$ es una solución de $ax+by=c$. Veamos que estas soluciones son las únicas.

Si $x_1,y_1$ es una solución, entonces tenemos $$ax_1+by_1=c=ax_0+by_0,$$ y entonces $$a(x_1-x_0)+b(y_1-y_0)=c-c=0,$$ de modo que $(x_1-x_0)$, $(y_1-y_0)$ es una solución de la ecuación homogénea $ax+by=0$, y por la proposición anterior, debe suceder que $x_1-x_0=-ka$ y $y_1-y_0=kb$ con $k$ un entero. Así, $x_1=x_0-ka$ y $y_1=y_0+kb$, como queríamos.

$\square$

Ejemplo 4. Determina todas las soluciones a la ecuación diofantina $12x+13y=1$.

Solución. Por inspección, una solución es $x=-1$, $y=1$. Los coeficientes de las variables son primos relativos. Por la proposición anterior, todas las soluciones son de la forma $-13k-1$, $12k+1$ donde $k$ es un entero arbitrario.

$\triangle$

Resumimos todo lo obtenido en el siguiente resultado.

Teorema. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero. Consideremos la ecuación diofantina $ax+by=c$. Si $M:=\text{MCD}(a,b)$ no divide a $c$, entonces la ecuación no tiene solución. Si sí, podemos usar el algoritmo de Euclides para encontrar una solución $x_0,y_0$. El resto de las soluciones son de la forma $x_0-ka’$, $y_0+kb’$, en donde $a’=a/M$, $b’=b/M$ y $k$ es cualquier entero.

Veamos un ejemplo en el que juntamos todo lo que ya sabemos.

Ejemplo 5. Determina todas las soluciones a la ecuación diofantina $21x-35y=14$.

Solución. Los coeficientes de las variables no son primos relativos, pues su máximo común divisor es $7$. Tenemos que $7$ divide a $14$, así que la ecuación sí tiene soluciones y son las mismas que las de la ecuación $3x-5y=2$. Por inspección, una solución es $x=-1, y=-1$. Así, todas las soluciones a esta ecuación (y por lo tanto a la original), son de la forma $x=5k-1, y=3k-1$.

$\triangle$

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. Resuelve el Ejemplo 2.
  2. En todos los ejemplos, verifica que las soluciones obtenidas en efecto son soluciones del sistema original.
  3. ¿Para cuántos enteros $c$ entre $1$ y $100$ se tiene que la ecuación lineal $21x+18y=c$ tiene solución $x,y$ en enteros?
  4. Sólo hemos visto ecuaciones diofantinas lineales en dos variables. Sin embargo, con lo visto hasta ahora puedes argumentar por qué la ecuación diofantina $91x+14y-70z=100$ no tiene soluciones en enteros. ¿Por qué?
  5. Investiga acerca de la ecuación pitagórica $x^2+y^2=z^2$.

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