Álgebra Superior II: Ecuaciones en congruencias

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

\square

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

\square

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.

\square

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

\square

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

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • 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.
  • Demuestra el corolario al Teorema 1.
  • Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
  • Diseña una ecuación lineal módulo 60 que tenga exactamente 15 soluciones módulo 60.
  • 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*}

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.