En un reloj, dar una vuelta completa nos devuelve a la misma posición. Las congruencias agrupan enteros cuya diferencia son vueltas completas de un tamaño fijo. Sumar y multiplicar respeta esas posiciones; dividir puede borrar información. Empezaremos con una clase en la recta y terminaremos resolviendo ecuaciones con ninguna, una o varias clases de solución.
Si necesitas repasar:
1. El módulo fija cuánto vale una vuelta completa
Fijamos un entero m≥2. a≡b módulo m significa que m divide a−b. Equivale a dejar el mismo resto normalizado, pero no exige que los dos enteros sean iguales. Puede haber representantes negativos.
Es equivalencia: a−a=0 da reflexividad; cambiar signo conserva múltiplos y da simetría; sumar diferencias da transitividad. La división con resto produce exactamente m clases, representadas por 0,…,m−1.
Las posiciones del dibujo son una misma clase
Compara −11,−3,5,13 módulo ocho.
Diferencias
Cada salto a la derecha añade ocho.
Respecto de cinco
−11−5=−16, −3−5=−8 y 13−5=8, todos múltiplos de ocho.Congruencia
Los cuatro representan la clase de cinco.
Son enteros distintos y congruentes módulo ocho.
Los representantes continúan infinitamente a ambos lados de la parte dibujada.
La misma diferencia puede servir para un módulo y no para otro
Compara veintiuno y tres.
Diferencia
21−3=18.Módulo seis
Seis divide dieciocho, luego 21≡3 módulo seis.
Módulo doce
Doce no divide dieciocho, así que no son congruentes módulo doce.
La congruencia depende del módulo escrito.
No se borra ni cambia el módulo al presentar la igualdad de clases.
2. Una clase es un conjunto infinito que tratamos como un objeto
Elegir un resto de cero a m−1 da una forma cómoda de escribir esa clase, sin eliminar los demás enteros que contiene.
Son múltiplos del módulo, por tanto las operaciones no dependen de representantes.
Escribir la clase completa
Describe [5] módulo ocho.
Parámetro
Es {5+8k:k∈ℤ}.Ejemplos
k=−2,−1,0,1 da −11,−3,5,13.Representante
Cinco es el único de esa clase entre cero y siete.
La clase contiene infinitos enteros, con un representante canónico.
No significa que el único entero admisible sea cinco.
Dos operaciones y otra elección de representantes
En módulo nueve, usa [4] y [8].
Suma
[4]+[8]=[12]=[3].Producto
[4][8]=[32]=[5].Otros
Trece representa [4] y menos uno representa [8]; suman doce y su producto −13 también es de clase cinco.
Las dos elecciones producen las mismas clases resultado.
La diferencia de productos es −13−32=−45, múltiplo de nueve, como exige la prueba general.
3. Podemos reducir después de cada suma o producto para evitar cifras enormes
Con el mismo módulo, las congruencias se conservan al sumar, restar, multiplicar y elevar a potencias enteras no negativas. Por eso podemos sustituir una base o un resultado intermedio por su resto sin cambiar el resultado final.
No reducimos el exponente módulo m usando solo esta regla: hace falta un período demostrado u otro teorema. Tampoco cambiamos libremente el módulo; si d divide m, una congruencia módulo m implica otra módulo d, pero no siempre al revés.
Una potencia grande con un período comprobado
Calcula 7⁵⁰ módulo diez.
Cuadrar
7²=49≡9; 7⁴≡9²=81≡1.Descomponer índice
50=4·12+2.Reducir
7⁵⁰=(7⁴)¹²7²≡1¹²·9=9.
El resto es 9.
Reducir el exponente cincuenta módulo diez habría dado cero y una respuesta incorrecta uno; el período usado era cuatro y se comprobó.
Pasar a un divisor del módulo
23≡9 módulo catorce.
Diferencia
23−9=14 es múltiplo de siete, así que también 23≡9≡2 módulo siete.
Conversa
23≡2 módulo siete es cierto porque la diferencia es veintiuno.
No ampliar
Esa diferencia no es múltiplo de catorce: 23 no es congruente con dos módulo catorce.
La implicación al módulo divisor no autoriza volver al mayor.
Declarar cuál es la diferencia evita deducciones basadas solo en la escritura de los restos.
4. Los divisores de cero muestran por qué no se cancela cualquier factor
En un módulo compuesto pueden existir clases no nulas cuyo producto sea cero. Si multiplicar pierde esa información, no podemos deshacerlo mediante una división ordinaria. Igualdad de productos no fuerza igualdad de los otros factores.
Si m es primo, todas las clases no nulas son invertibles y la estructura es un cuerpo. Si m es compuesto, algunas siguen siendo invertibles, pero otras no. La coprimalidad con m, no solo ser distinto de cero, decide la diferencia.
Un producto cero y una cancelación falsa
Trabaja módulo ocho.
Producto
[2][4]=[0] y ninguno de esos factores es cero.Igualdad
2·1≡2·5, porque ocho divide diez menos dos.
No cancelar sin más
Uno y cinco no son congruentes módulo ocho.
El factor dos no se puede cancelar manteniendo módulo ocho.
Ser clase no nula no implica tener inverso cuando el módulo es compuesto.
Un módulo compuesto también tiene unidades
La clase de tres módulo ocho.
Producto
3·3=9≡1.Inverso
Tres es su propio inverso.
Deshacer
Si 3a≡3b módulo ocho, multiplicar por tres da a≡b.
Tres sí permite cancelar en ese mismo módulo.
No se aplica una regla global todos cancelan o ninguno cancela; depende del coeficiente.
5. Bézout construye inversos exactamente cuando el mcd es uno
Recíprocamente, un inverso produce au−km=1 y cualquier divisor común de a,m debe dividir uno.
El inverso es único como clase, aunque su representante pueda cambiar por múltiplos de m. Un coeficiente negativo de Bézout es válido; lo normalizamos al final y comprobamos el producto. Si el mcd no es uno, no buscamos un inverso inexistente.
Un inverso obtenido por restos
Invierte siete módulo veintiséis.
Euclides
26=3·7+5; 7=5+2; 5=2·2+1.Volver
1=5−2(7−5)=3·5−2·7.Entradas originales
1=3(26−3·7)−2·7=3·26−11·7.Normalizar
El inverso −11 representa quince módulo veintiséis.
7⁻¹≡15 módulo veintiséis.
7·15=105=4·26+1 comprueba la cuenta.
Un coeficiente sin inverso
Ocho módulo doce.
Mcd
mcd(8,12)=4.Condición
Si 8u≡1, existiría 8u−12k=1.Contradicción
El lado izquierdo es múltiplo de cuatro y uno no lo es.
La clase de ocho no tiene inverso módulo doce.
Bézout puede producir el mcd cuatro, pero no un uno que contradiga ese divisor común.
6. Cancelar sin unidad reduce el módulo según el mcd
Si c es unidad, ac≡bc módulo m equivale a a≡b en el mismo módulo. En general, d=mcd(c,m) y m∣c(a−b) equivale a (m/d)∣a−b: tras retirar d, c/d es coprimo con m/d.
Por tanto cancelar c produce a≡b módulo m/d. Si d>1, mantener el módulo anterior impone una condición demasiado fuerte y puede perder soluciones. El caso m/d=1 no restringe a−b: todos los enteros son congruentes con ese módulo reducido.
Cancelar una unidad conserva el módulo
9x≡9·5 módulo catorce.
Mcd
Nueve y catorce son coprimos.
Inverso
9·11=99≡1 módulo catorce.Cancelar
Multiplicar ambos lados por once da x≡5 módulo catorce.
Hay una sola clase x≡5 en ese módulo.
La operación es reversible porque se usó un inverso.
Cancelar otro coeficiente cambia el módulo
8x≡8·1 módulo doce.
Común
mcd(8,12)=4.Módulo nuevo
Cancelar ocho da x≡1 módulo 12/4=3.No perder
En módulo doce incluye 1,4,7,10; por ejemplo x=4 produce 32≡8.
La condición correcta es x≡1 módulo tres.
Conservar solo x≡1 módulo doce habría descartado tres clases que sí cumplían la congruencia original.
7. Una ecuación modular lineal es una ecuación entera con una incógnita auxiliar
Si d=mcd(a,m), el lado izquierdo siempre es múltiplo de d; si d no divide b, no hay solución.
Si d divide b, Bézout au+mv=d, multiplicado por b/d, da una solución x=u(b/d). Esta es una prueba de existencia, todavía no una enumeración completa. Con un coeficiente no invertible puede haber varias clases en el módulo original.
Construir una solución sin suponer que el coeficiente tiene inverso
6x≡9 módulo quince.
Existencia
El mcd es tres y divide nueve.
Bézout
3=15−2·6; al multiplicar por tres, 9=3·15−6·6.Leer
x=−6, que representa nueve módulo quince, es una solución.
Ya hay una solución, pero todavía faltaría describir todas.
6·9=54≡9 módulo quince; la verificación vuelve al módulo original.
Una condición imposible
8x≡3 módulo doce.
Mcd
El divisor común es cuatro.
Divisibilidad
Toda cantidad 8x−12k es múltiplo de cuatro.
Segundo miembro
Tres no lo es.
No existe ninguna clase solución.
No se intenta dividir por ocho ni buscar su inverso en un caso donde el criterio ya descarta existencia.
8. La clase reducida se levanta a exactamente d clases del módulo original
Cuando d|b, dividimos coeficiente, segundo miembro y módulo entre d. La nueva congruencia (a/d)x≡b/d módulo m/d tiene coeficiente coprimo con su módulo y, si m/d>1, una única clase reducida x≡x₀.
En el módulo original aparecen x₀,x₀+m/d,…,x₀+(d−1)m/d: son d clases distintas. Toda solución reducida tiene una de esas formas al reducir el parámetro módulo d. Si m/d=1, no necesitamos un inverso: todos los enteros son solución y corresponden a las m clases originales.
Las tres clases del dibujo
Resuelve por completo 6x≡9 módulo quince.
Reducir
d=3: queda 2x≡3 módulo cinco.Invertir
El inverso de dos es tres: x≡9≡4 módulo cinco.
Levantar
Sumamos pasos de cinco en módulo quince: 4,9,14.
Contar
Hay tres clases, exactamente el mcd.
x≡4,9 o 14 módulo quince, o x=4+5t como familia entera.
Sus productos por seis son 24,54,84; todos dejan resto nueve al dividir por quince.
El módulo reducido uno significa ausencia de restricción
12x≡24 módulo doce.
Mcd
d=12 y divide veinticuatro.Directo
12x−24=12(x−2), múltiplo de doce para cualquier entero x.Clases
Son solución los doce restos 0,1,…,11.
Todos los enteros resuelven la congruencia.
No se fuerza un procedimiento de inversos módulo uno; la condición es una identidad de divisibilidad.
9. Una solución comprobada no es todavía una respuesta exhaustiva
Para comunicar el resultado distinguimos una clase del módulo original, varias clases o una familia de enteros. La comprobación final usa siempre el módulo del enunciado. El número de clases previsto por el mcd ayuda a detectar las que faltan.
Una ecuación reducida solo es equivalente cuando la cancelación y el nuevo módulo están justificados. Si el coeficiente era invertible hay una clase; si no lo era, comprobar un representante favorable no demuestra unicidad.
Por qué encontrar nueve no completaba el ejemplo
En 6x≡9 módulo quince habíamos obtenido x≡9.
Es válida
Seis por nueve deja resto nueve.
No es única
Cuatro también cumple, pero no es congruente con nueve módulo quince.
Completar
La respuesta completa son las tres clases 4,9,14, equivalentes a x≡4 módulo cinco.
La existencia de una solución y la descripción de todas son etapas distintas.
El mcd tres predecía tres clases cuando el segundo miembro era compatible.
Una respuesta única con todos sus enteros
Resuelve 5x≡4 módulo trece.
Inverso
5·8=40≡1, así que x≡8·4=32≡6.Enteros
Todos son x=6+13k.Comprobar
5(6+13k)−4=13(2+5k), múltiplo de trece para todo k.
x≡6 módulo trece, una clase completa.
El representante −7 corresponde a k=−1 y también sirve; no se descartan soluciones por ser negativas.
Ahora lo resolvemos de principio a fin.
EJEMPLO RESUELTO 1
Un inverso
Resuelve 3x≡2 mod 7.
Datos
3x≡2 módulo siete.
Mcd
7=2·3+1 demuestra coprimalidad y una única clase solución.
Inverso
1=7−2·3 da inverso −2, equivalente a cinco.Multiplicar
5·3x≡5·2, de donde x≡10.
Reducir
x≡3 módulo siete.
Exhaustividad
Multiplicar por un inverso es reversible.
Los enteros son 3+7k, y 3(3+7k)−2=7(1+3k) verifica todos.
x≡3 mod 7.
3·3=9 y 9−2=7, divisible por siete. También 3(3+7k)−2=7(1+3k) para todo k entero.
EJEMPLO RESUELTO 2
Dos clases de solución
Resuelve 2x≡4 mod 6.
Común
mcd(2,6)=2 divide cuatro, así que existen soluciones.
Divisibilidad
6|2(x−2) equivale a 3|x−2.
Cancelar correctamente
La congruencia reducida es x≡2 módulo tres.
Familia
x=2+3k, k entero.Levantar
k par produce [2] módulo seis y k impar produce [5].
Completar
Son dos clases distintas, como predice el mcd: 2·2≡4 y 2·5≡4 módulo seis.
x≡2 o 5 mod 6.
Para x=2 el producto es cuatro; para x=5 es diez, que deja resto cuatro al dividir por seis. Ambas clases satisfacen la congruencia original.
Los símbolos que hemos usado
- a≡b (mod m)
- m divide a−b; a y b representan el mismo resto para el módulo positivo m.
- [a]
- Clase de todos los enteros congruentes con a para el módulo que se haya fijado.
- Z/mZ
- Anillo de clases de enteros módulo m con suma y producto heredados.
- a⁻¹ (mod m)
- Clase u que cumple au≡1 módulo m, cuando existe.
- d=mcd(a,m)
- Divisor que determina existencia y número de soluciones de una congruencia lineal.
- Representante canónico
- Único entero de una clase entre cero y m−1.
Ahora te toca a ti.
Tienes cinco ejercicios. Inténtalos; las pistas te ayudan si te atascas.
Practicar este tema →