Archivo de la etiqueta: combinaciones enteras

Álgebra Superior II: Ecuaciones diofantinas

Por Leonardo Ignacio Martínez Sandoval

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»