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(\mathrm{mod}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$.

$\mathrm{△}$

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(\mathrm{mod}7)$?

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

$\mathrm{△}$

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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}n).$$ Multiplicando ambos extremos de esta ecuación por $a^{-1}$, tenemos que $$x\equiv a^{-1}ax\equiv a^{-1}ay\equiv y(\mathrm{mod}n).$$

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}8)$ y a la ecuación $4x\equiv 0(\mathrm{mod}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(\mathrm{mod}8)$.

$\mathrm{△}$

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(\mathrm{mod}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^{\prime }=a/M$, $b^{\prime }=b/M$ y $n^{\prime }=n/M$ (con $a^{\prime }$, $b^{\prime }$, $n^{\prime }$ enteros). El entero $x$ es solución a la ecuación en congruencias $ax\equiv b(\mathrm{mod}n)$ si y sólo si es solución a la ecuación en congruencias $a^{\prime }x\equiv b^{\prime }(\mathrm{mod}{n}^{\prime })$.

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

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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(\mathrm{mod}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^{\prime }:=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^{\prime }x\equiv b^{\prime }(\mathrm{mod}{n}^{\prime })$, en donde $a^{\prime }=a/M$ y $b^{\prime }=b/M$. En esta ecuación, $a^{\prime }$ y $n^{\prime }$ son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo $n^{\prime }$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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^{\prime }$. 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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}30)$.

$\mathrm{△}$

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^{\prime }=a/M$ y $n^{\prime }=n/M$. Muestra que $\text{MCD}(a^{\prime },n^{\prime })=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{array}{rl}x& \equiv -1(\mathrm{mod}77)\\ x& \equiv -1(\mathrm{mod}55)\end{array}$$

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»