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. Ya que tenemos un buen manejo de la aritmética en congruencias, podemos comenzar a hacernos preguntas acerca de las ecuaciones que pueden se plantear y resolver en estos términos.

Ejemplo 1. ¿Cuáles son las soluciones enteras a la ecuación $x\equiv 3 \pmod 6$?

Solución. Un número $x$ satisface la ecuación si y sólo si $6$ divide a $x-3$, lo cual sucede si y sólo si $x$ es de la forma $x=6r+3$, donde $r$ es un número entero. Así, el conjunto de soluciones es de la forma $$6\mathbb{Z}+3:= \{6r+3: r\in \mathbb{Z}\}.$$ Dicho de otra forma, el conjunto de soluciones es la clase de equivalencia del $3$ módulo $6$, es decir, $[3]_6$.

$\triangle$

Cuando tengamos ecuaciones más complicadas, usualmente lo que haremos es dejar expresada la solución en términos de congruencias, es decir, como uno o varios elementos de $\mathbb{Z}_n$. Si se quiere encontrar a todos los enteros (en $\mathbb{Z}$) que sean solución, basta recordar este ejemplo para expresar a las soluciones en $\mathbb{Z}_n$ como conjuntos de soluciones en $\mathbb{Z}$.

Ejemplo 2. ¿Cuáles son las soluciones enteras a la ecuación $2x+1\equiv 0 \pmod 7$?

Solución. Trabajemos módulo $7$. Restando $1$ de ambos lados obtenemos $$2x\equiv -1\equiv 6 \pmod 7.$$ Multiplicando por $4$ de ambos lados tenemos que $$8x\equiv 24\equiv 3\pmod 7.$$ Como $8x\equiv x \pmod 7$, tenemos que $x\equiv 3 \pmod 7$ es la solución.

$\triangle$

En el ejemplo anterior encontramos las soluciones módulo $7$. Si queremos encontrar las soluciones en enteros, basta expresar esta congruencia en términos de enteros: las soluciones en $\mathbb{Z}$ son los números de la forma $7r+3$ con $r$ entero.

Ecuaciones lineales en congruencias

Una ecuación lineal en congruencias es de la forma $$ax\equiv b\pmod n.$$ Vamos a estudiar esta ecuación, viendo cuándo tiene solución y cuántas soluciones módulo $n$ tiene. Hay un caso fácil de estudiar, que es cuando $a$ y $n$ son primos relativos.

Proposición 1. Sean $a,b$ enteros y $n$ un entero positivo tales que $\text{MCD}(a,n)=1$. Entonces la ecuación $$ax\equiv b \pmod n$$ tiene una única solución $x$ módulo $n$.

Demostración. Como $a$ y $n$ son primos relativos, $a$ tiene un inverso multiplicativo módulo $n$, digamos $a^{-1}$. Afirmamos que $x=a^{-1}b$ es solución. En efecto, $a(a^{-1}b)\equiv 1\cdot b\equiv b \pmod n$.

Ahora, afirmamos que la solución es única. Supongamos que $x$ y $y$ son solución. Tendríamos entonces que $$ax\equiv b \equiv ay \pmod n.$$ Multiplicando ambos extremos de esta ecuación por $a^{-1}$, tenemos que $$x\equiv a^{-1}ax\equiv a^{-1}a y \equiv y \pmod n.$$

$\square$

Sin embargo, como ya vimos antes, no siempre pasa que todo elemento tenga inverso multiplicativo. Necesitamos un análisis más detallado.

Notemos que $x$ es solución de $ax\equiv b\pmod n$ si y sólo si $n$ divide a $ax-b$, lo cual sucede si y sólo si existe un entero $y$ tal que $ax-b=ny$. Reordenando, tenemos que $ax-ny=b$. En otras palabras, la ecuación en congruencias tiene solución si y sólo si podemos expresar a $b$ como combinación lineal entera de $a$ y $n$, lo cual sucede si y sólo si $$b\in a\mathbb{Z} + n \mathbb{Z}=\text{MCD}(a,n)\mathbb{Z},$$ es decir, si y sólo si $b$ es múltiplo del máximo común divisor de $a$ y $n$. Resumimos esta primer parte del análisis en la siguiente proposición.

Proposición 2. 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 $\text{MCD}(a,n)$ divide a $b$.

Ahora, queremos entender cuántas soluciones diferentes hay módulo $n$.

Ejemplo. Encuentra todas las soluciones a la ecuación $4x\equiv 1 \pmod 8$ y a la ecuación $4x\equiv 0 \pmod 8$.

Solución. Tenemos que $\text{MCD}(4,8)=4$ y que $4$ no divide a $1$, así que la primer ecuación no tiene solución. Tenemos que $4$ sí divide a $0$, así que la segunda ecuación sí tiene solución. Veamos cuántas tiene.

Notemos que al multiplicar por $4$ cada uno de los elementos $0,2,4,6$ obtenemos respectivamente $0,8,16,24$, que son todos múltiplos de $8$, así que estos elementos de $\mathbb{Z}_8$ son solución. Al multiplicar $4$ por $1,3,5,7$ obtenemos $4,12,20,28$, que módulo $8$ son $4,4,4,4$, así que ninguno de estos números son solución. Así, las soluciones son $x\equiv 0,2,4,6\pmod 8$.

$\triangle$

Una forma alternativa de expresar la solución del problema anterior es darse cuenta de que las soluciones en enteros son los números pares, o bien los enteros $n$ tales que $n\equiv 0\pmod 2$. En general, cuando la solución existe, podemos encontrar un módulo en la que la podemos describir de manera única. Este es el contenido de las siguientes dos proposiciones.

Proposición 3. Sean $a,b$ enteros y $n$ un entero positivo tales que $M=\text{MCD}(a,n)$ divide a $b$. Sean $a’=a/M$, $b’=b/M$ y $n’=n/M$ (con $a’$, $b’$, $n’$ enteros). El entero $x$ es solución a la ecuación en congruencias $ax\equiv b \pmod n$ si y sólo si es solución a la ecuación en congruencias $a’x\equiv b’\pmod {n’}$.

Demostración. Tenemos que $x$ es solución a $ax\equiv b \pmod n$ si y sólo si existe una combinación lineal entera $ax-ny=b$. Al dividir entre $M\neq 0$, esto sucede si y sólo si $a’x-n’y=b’$, lo cual sucede si y sólo si $x$ es solución a la ecuación en congruencias $a’x\equiv b’\pmod {n’}$.

$\square$

Estamos listos para enunciar el resultado principal de esta sección. Viene de la combinación de las ideas anteriores.

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

Demostración. La primer parte es la Proposición 2. Una vez que sabemos que la ecuación tiene solución, por la Proposición 3 podemos encontrar la ecuación equivalente $a’x\equiv b’\pmod {n’}$, en donde $a’=a/M$ y $b’=b/M$. En esta ecuación, $a’$ y $n’$ son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo $n’$.

$\square$

Como empezamos con una ecuación módulo $n$, quizás queremos saber cuántas soluciones tiene módulo $n$, y no módulo $n’$. De manera inmediata, obtenemos el siguiente resultado.

Corolario. Con la notación del teorema anterior, cuando la ecuación tiene solución, entonces tiene $M$ soluciones módulo $n$.

Ejercicio. Resuelve la ecuación lineal en congruencias $$12x\equiv 18 \pmod {30}.$$

Intenta resolver este ejercicio antes de ver la solución. Puedes comenzar calculando el máximo común divisor de $12$ y $30$.

Solución. El máximo común divisor de $12$ y $30$ es $6$, que sí divide a $18$. Entonces sí hay soluciones, y habrá $6$ soluciones módulo $30$. Para encontrar la ecuación reducida equivalente, dividimos entre $6$ para obtener $$2x\equiv 3 \pmod 5.$$

El inverso de $2$ módulo $5$ es $3$. Multiplicando en ambos lados por $3$ obtenemos la solución $$x\equiv 9 \equiv 4 \pmod 5.$$

Para recuperar las soluciones módulo $30$, a cada una de estas soluciones le sumamos $30/6=5$ repetidamente para obtener las soluciones $x\equiv 4, 9, 14, 19, 24, 29 \pmod {30}$.

$\triangle$

En la siguiente entrada veremos cómo resolver sistemas de ecuaciones lineales en los que tenemos más de una congruencia.

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. Sea $a$ un entero y $n$ un entero positivo. Sea $M=\text{MCD}(a,n)$ y sean $a’=a/M$ y $n’=n/M$. Muestra que $\text{MCD}(a’,n’)=1$.
2. Demuestra el corolario al Teorema 1.
3. Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
4. Diseña una ecuación lineal módulo $60$ que tenga exactamente $15$ soluciones módulo $60$.
5. Para prepararte para la siguiente entrada, intenta resolver por completo el sistema de congruencias

\begin{align*}
x&\equiv -1 \pmod{77}\\
x&\equiv -1 \pmod{55}\\
\end{align*}

Entradas relacionadas

• Ir a: Álgebra Superior II
• Entrada anterior del curso: Problemas que usan teoremas de Fermat y Wilson
• Entrada siguiente del curso: Teorema chino del residuo

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»