 |
Aprender y divertirse con
la Hoja de Cálculo Página personal de Antonio Roldán Martínez |
Inicio Sin decimales Aritmética Divisibilidad Combinatoria Congruencias Juegos Diccionario general Estadística |
|
Congruencias Teoría Propuestas Diccionario Herramientas Páginas de interés |
||
|
Estás en Inicio > Sin decimales > Congruencias > Teoría |
||
"La mejor forma de librarse de un problema es resolverlo" Francis Brendan
 |
Congruencias |
Breve esquema teórico |
Todo el tema de congruencias se desarrolla en el conjunto de los números enteros, pero por simplicidad, y para facilitar el uso con alumnos, haremos mención sólo de los naturales en los ejemplos, aunque los resultados se generalizan fácilmente.
No se demuestra ningún resultado, ya que el objetivo de estos apuntes es tan solo mostrar un recorrido breve por los aspectos teóricos más interesantes.
Definición
Dos números enteros a y b se llaman congruentes respecto
a un número natural m llamado módulo, cuando
a - b es divisible entre m, y se escribe a = b (mod m)
También se puede expresar esta situación como que ambos
números dan el mismo resto al dividirlos entre m.
A la relación que se establece entre ambos la llamaremos congruencia.
Por ejemplo, son válidas las congruencias 8 = 13 (mod 5) 129 = 229 (mod 100)
Este concepto fue introducido por K.F. Gauss en su obra Disquisitionae Arithmeticae
Propiedades
* Para que sea a = b (mod m) es necesario y suficiente que exista un h entero tal que a = b + hm.
* Todos los múltiplos de m son congruentes con 0.
* Si a=b (mod m) y a es primo con m, también lo será b.
* Si a=b (mod m), entonces an=bn (mod m)
* Si n divide a a,b y m, y a=b (mod m), se tiene que a/n = b/n (mod m/n)
* Si n divide a a y b y es primo con m, y además a=b (mod m), se tiene que a/n = b/n (mod m)
* Si n divide a a y b y el MCD(n,m)=d, y además a=b (mod m), se tiene que a/n = b/n (mod m/d)
* Si a=b (mod m) y c=d (mod m) , entonces:
* Si dos números a y b son congruentes respecto a varios módulos, también lo serán respecto a su mínimo común múltiplo.
* Si dos números a y b son congruentes respecto a un módulo m, también lo serán respecto a todos los divisores de m.
* La congruencia es una relación de equivalencia, porque es:
* Si en un polinomio con indeterminada x y coeficientes todos enteros, se sustituyen todos los elementos dos veces mediante pares de valores congruentes respecto a un módulo, los valores numéricos resultantes también serán congruentes respecto a ese módulo. Así: 2.22+3.2+7= 21 es congruente con 2.72+3.7+2=121 respecto al módulo 5.
Esta propiedad resume muchas anteriores y permite, por ejemplo, la prueba del 9 en las operaciones aritméticas.
Si la congruencia es una relación de equivalencia, permitirá clasificar a los números enteros (y por tanto a los naturales) en clases de equivalencia, conjuntos formados por cada número entero y todos sus congruentes. En este caso se llaman clases de restos o residuales, porque cada clase se puede representar por el resto que resulta al dividir cualquier elemento entre el módulo m.
Las clases módulo m se representan por Z/mZ, o por Zm. Así:
Z/2Z = {0,1}, que son los dos restos producidos al dividir entre 2. El elemento 0 representa a los números pares y el 1 a los impares.
Z/5Z = {0,1,2,3,4}, en la que, por ejemplo el elemento 3 representa a los números 3, 8, 13, 18, 23, ... que dan resto 3 al dividirlos entre 5
La clase Z/mZ contiene exactamente m elementos: {0,1,2,3,...m-1}. A veces se usan restos mínimos, admitiendo números positivos y negativos, mediante la elección entre a y a-m del número con menor valor absoluto. Por ejemplo, Z/5Z se podría representar como {0,1,2,-2,-1}
Vimos en el apartado anterior la compatibilidad de la suma y el producto con la relación de congruencia:
Si a=b (mod m) y c=d (mod m) , entonces:
Estas dos propiedades nos permiten definir la suma y el producto entre clases de restos: sumar o multiplicar dos clases equivaldrá a efectuar la operación entre los restos correspondientes a cada clase.
En Informática la función MOD convierte un número en su resto respecto a un módulo dado. En las hojas de cálculo se usa la función RESIDUO.
Estructura algebraica
Las clases de restos tienen estructura de anillo para la suma y el producto. El grupo aditivo de ese anillo es cíclico, pues para cada elemento a del mismo existe un h tal que a.h = 0. Ese número h ha de ser divisor del módulo m.
No todos los elementos tienen inverso. En caso afirmativo,
se llaman inversibles, y su conjunto coincide con las
clases representadas por
números primos con m, incluyendo el 1. Por tanto, su número coincide con
el indicador de Euler
del módulo.
Una fórmula para calcular el inverso de un número a es
a-1=af(m)-1, siendo f(m) el indicador del módulo
m.
Así, en Z/12Z, son inversibles las clases 1,5,7 y 11.
Los elementos inversibles forman un grupo multiplicativo, al que
representaremos por Z*m. Intenta demostrarlo. También llamaremos a los
elementos de este grupo, las clases residuales reducidas.
Este carácter de grupo da lugar a una propiedad muy sencilla:
Si a es inversible en Z/mZ, existe un número natural r tal que ar=1
El número r mínimo que cumple la anterior igualdad se llama,
como en todos los grupos, orden, índice o gaussiano de a.
Es fácil ver que si a x =1 (mod m), el exponente x
deberá ser múltiplo del orden r.
Otra consecuencia es que si a es primo con m y se cumple que a x =
a y , entonces han de ser x = y.
Si m es primo, serán inversibles todos los elementos y constituirán un cuerpo.
Sistemas de restos
Un conjunto de números enteros forma un sistema de números incongruentes respecto a un módulo m, cuando cada uno de ellos produce un resto distinto al dividirlo entre m. Por ejemplo, 13, 26, 36 y 78 forman un sistema de números incongruentes módulo 12, pues producen los restos 1, 2, 0 y 6 respectivamente.
Los restos módulo m sólo pueden ser los elementos del conjunto {0,1,2,...m-1} que constituyen un sistema completo de restos. Por analogía, llamaremos sistema completo de números incongruentes a un conjunto de m números enteros que produzcan todos los restos posibles desde 0 hasta m-1. Por ejemplo, {21, 6, 15, 4} forman ese tipo de sistema respecto al módulo 4.
Un conjunto de m elementos incongruentes siempre es completo.
Si se forma un conjunto sólo con los números primos con m, el sistema formado se llama reducido. Su número es el indicador de Euler.
La propiedad fundamental de estos conjuntos es:
Si los elementos de un sistema de números incongruentes (mod m) se multiplican todos por un mismo número primo con m y se les suma después un mismo número a todos, el resultado será otro sistema de números incongruentes.
Es evidente que si el primer sistema es completo, también lo será el segundo. Por ejemplo, el sistema {3,4,5,6,7}, completo respecto a 5, se transforma mediante la función 3.n+2 en {11,14,17,20,23}, que produce los restos {1,4,2,0,3}, por cierto que en distinto orden.
Mediante estos sistemas (no lo haremos aquí), se pueden demostrar dos teoremas fundamentales:
Si llamamos f(m) al indicador de Euler de m, se cumplirá que af(m)=1 (mod m) para todo a primo con m. (Teorema de Euler)
Si m es primo, la igualdad anterior se puede expresar como am-1=1 (mod m) (Teorema de Fermat)
También es interesante formular el Teorema de Fermat, o Pequeño Teorema, como am=a (mod m)
El recíproco no es cierto. Si para un a primo con m se cumple am-1=1 (mod m), entonces m no tiene que ser necesariamente primo. A estos números compuestos que cumple el teorema les llamaremos pseudoprimos. Hay algunos pseudoprimos que cumplen la condición am-1=1 (mod m) para todos los números primos con él . A estos números se les llama de números de Carmichael o pseudoprimos absolutos.
Llamaremos Restos potenciales del número natural n
respecto a un módulo dado m a los restos producidos por las distintas
potencias naturales de n. Por ejemplo, los restos potenciales de 5 respecto
al módulo 3 son:
De 50 el resto es 1, de 51 el resto es 2, de 52 el 1,
de 53 el 2, etc. y así siguen de forma periódica.
El conjunto de restos potenciales sigue unas pautas muy sencillas:
Un elemento a de unas clases de restos de módulo m, con a primo con m. es resto cuadrático cuando es resto potencial de algún cuadrado, es decir, que existe un n tal que n2 = a (mod m). En caso contrario diremos que a es no resto cuadrático. Bastará ensayar los cuadrados de los números 0,1,2,3...m-1 para ver si alguno de ellos produce de resto a. En realidad sólo hay que probar la mitad, pues r produce el mismo resto cuadrático que m-r. Intenta demostrarlo.
Por ejemplo, con módulo 8, son restos cuadráticos 0, 1 y 4 y son no restos cuadráticos 2,3,5,6 y 7.
El caso más interesante se presenta cuando m es primo. En este caso se verifican estas propiedades:
Por ejemplo, si m=11, los restos son 1, 3, 4, 5 y 9 y los no restos 2, 6,7, 8 y 10 (o bien -1, -3, -4, -5 y -9). Los restos forman un grupo, como se puede verificar fácilmente.
Símbolo de Legendre
Si m es primo, y a primo con él (es decir, no múltiplo, en este caso) usaremos el símbolo (a/m) (símbolo de Legendre) para indicar si a es resto cuadrático o no respecto a m. Si lo es, declararemos que (a/m)=1, y si no lo es, que (a/m)=-1 (Escribimos el símbolo de forma inclinada, pero se suele escribir verticalmente como una fracción)
Según lo expuesto, se tendrá que (ab/m)=(a/m)(b/m), y que la asignación de +1 o -1 es un verdadero homomorfismo entre Z/Zp y el grupo multiplicativo {+1,-1}, tal como se anunció en párrafos anteriores.
Ley de reciprocidad cuadrática de Gauss (ya descubierta por Legendre)
Si p y q son primos impares, y uno de ellos tiene la forma 4n+1, entonces p es resto cuadrático respecto de q si y solo si q es resto cuadrático de de p. Si ambos presentan la forma 4n+3, si p es resto cuadrático de q, entonces q no lo es de p, y a la inversa.
Si se usa el símbolo de Legendre, la ley se puede expresar así:
En ese caso, si uno de los dos, p o q, tienen la forma 4n+1, la potencia tiene el valor de 1, por lo que si p es resto cuadrático de q, ocurrirá también que q lo será de p. Si ambos tienen la forma 4n+3, la potencia valdrá -1, y si p es resto de q, q no lo será de p.
Criterio de Euler
Los símbolos de Legendre nos ayudan a expresar un criterio debido a Euler para saber si un entero es resto cuadrático:
Sea m primo y a entero coprimo con él. Entonces se cumple:
Lo podemos comprobar, por ejemplo, con los restos respecto a 11.
55 = 3125 = 1 (mod 11, luego 5 sí es resto cuadrático.
75 = 16807 = 10 (mod 11 = -1 (mod 11, luego 7 no es resto cuadrático.
Ecuación lineal en congruencias
Llamaremos ecuación lineal a la de forma a*x = b (mod m). Los tipos de solución que presenta son:
Sistemas de ecuaciones lineales
Sólo se incluye el caso del llamado Teorema Chino:
Si A1, A2, …An son números enteros que son primos entre sí dos a dos y a1, a2, a3,…an, enteros cualesquiera, existe un número entero N que cumple N=ai (mod Ai) para todo i entre 1 y n. Todas las demás soluciones del sistema son congruentes con N con módulo igual al producto de los módulos.
Para calcular ese número se sigue el proceso:
Por ejemplo: Encontrar un número n tal que al dividirlo entre 10 nos dé de resto 7, y al dividirlo entre 9 obtengamos un resto de 3.
H=9.10 = 90 ; A’1=9 ; A’2=10 ; m1=9 ; m2=1 y por último:
N=9.7.9+10.3.1= 597.
Para encontrar las demás soluciones bastará con ir sumando H=90: 597, 687, 777, 867, ...
Ecuaciones polinómicas en Zm
Al ser Zm un anillo, será posible definir polinomios con una indeterminada. Esto permite definir ecuaciones polinómicas como la siguiente:
f(x) = a n x n + a n-1 x n-1 + ... a 1 x + a 0 = 0 (mod m)
Para este tipo de ecuaciones es cierto el
Teorema de Lagrange
Si en la ecuación polinómica f(x) = a n x n + a n-1 x n-1 + ... a 1 x + a 0 = 0 (mod m) el módulo m no divide a todas las a i , entonces el número de soluciones de la ecuación no puede ser superior a m.
Definición
Ya hemos visto, que según el Teorema de Euler, para cada elemento inversible a de Zm existe un índice u orden g, que es el mínimo exponente que cumple la condición ag = 1 (m, y que este valor g es divisor de la función de Euler f(m). Entre estos elementos puede haber algunos en los que g coincida con f(m). A estos elementos les llamaremos raíces primitivas módulo m.
Por ejemplo, con módulo 7, los índices g de cada elemento son: i(1)=1, i(2)=3, i(3)=6, i(4)=3, i(5)=6, i(6)=2. Puedes comprobar que en cada caso ai(a)=1. Podemos observar que son raíces primitivas el 3 y el 5, cuyo índice o gaussiano es f(7)=6.
Una propiedad importante de las raíces primitivas es que sus potencias engendran todo el grupo reducido. En el caso del 3, módulo 7, se verificaría: 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1.
Otro ejemplo: en módulo 12 los elementos inversibles son {1,5,7,11} Sus índices son i(1)=1, i(5)=2, i(7)=2, i(11)=2, luego el módulo 12 no tiene raíces primitivas. Se puede demostrar que sólo los módulos 2, 4 y los del tipo pa o 2pa con p primo poseen raíces primitivas.
Logaritmo discreto
Si una raíz primitiva engendra todo el grupo de inversibles, cada uno de estos vendrá representado por su exponente respecto a esa raíz primitiva. Es decir, que si a es raíz primitiva y b un elemento inversible, existirá un exponente g tal que ag = b. A ese número g le llamaremos logaritmo discreto o índice de b con base a.
En el ejemplo anterior de módulo 7. la raíz 3 engendra mediante potencias todos los elementos desde 1 a 6 (por ser 7 primo son todos inversibles), lo que da lugar a poder definir logaritmos discretos para todos ellos. Por ejemplo, como 34 = 4, tendremos que loga(4) = 4.
Otros temas relacionados con las congruencias
Estos temas se desarrollan de forma sucinta, tan sólo para presentarlos. Si deseas adquirir más conocimientos debes acudir a manuales o direcciones de Internet que los tratan.
Las congruencias nos permiten generar números naturales, que aunque procedentes de fórmulas o algoritmos, semejan haber sido generados al azar.
Una técnica muy sencilla para ello es la siguiente:
En los ordenadores, la semilla se toma del estado actual del reloj interno, lo que aumenta la sensación de aleatoriedad.
Como ejemplos de generadores populares podemos recordar dos:
Si a=75, c=0 y m=231 - 1, resulta el generador usado
durante muchos años por IBM y el programa MATLAB
Si a=1103515425, c=12345 y m=232, obtendremos el generador del
sistema UNIX
Temas de calendarios
Los calendarios están formados por múltiples congruencias y todos los elementos fundamentales de la hora, día y año pertenecen a las clases Z/mZ. Por ejemplo:
E igual con los siglos, los años terminados en 0 no bisiestos, etc.
Los criterios que estudiábamos de niños (Un número es divisible entre 9 si la suma de sus cifras...) están basados en los restos potenciales.
Si deseamos ver si el número abcde es divisible entre m, podríamos descomponer ese número en unidades, decenas, centenas, de la forma
abcde = a104 + b103 + c102+d10+e con lo que el resto de dividirlo entre m, según los teoremas de las congruencias, equivale a
Resto: (ar4 + br3 + cr2 + dr1 + er0) (mod m) (1)
siendo r4,r3... los restos potenciales de 10 respecto a m.
Estos restos pueden ser:
Módulo 2: r0=1, r1=0,r2=0, r3=0,... La expresión (1) se reduce a a MOD m
En el criterio sólo habrá que mirar las unidades, que corresponden al único resto no nulo.
Módulo 3: r0=1, r1=1,r2=1, r3=1,... Todos los restos valen 1. En este caso la expresión (1) del resto será a +b +c +d +e MOD m
por lo que habrá que sumar todas las cifras y ver su resto respecto a m
y así con todos.
No es imprescindible usar el número 10. Con el número 1000 se pueden construir criterios para el 13, 11 y 7, porque sus restos potenciales son r0=1, r1=1,r2=1, r3=1,...lo que permite usar sumas alternadas de números de tres cifras.
Cálculo con números grandes
El Teorema Chino nos garantiza que dados A1, A2, …An primos entre sí dos a dos, todo número natural menor que A1* A2* …*An viene determinado por a1, a2, a3,…an, tales que que cumple N=ai (mod Ai) para todo i entre 1 y n. Esto nos permite representar N de forma unívoca por el vector (a1, a2, a3,…an)
Por ejemplo, 9 y 10 son primos entre sí, luego todos los números menores que su producto 90 vendrán representados de forma unívoca por sus restos respecto a ellos. Así, el número 57 se representaría por el par de coordenadas (3,7), porque 57=3(mod9 y 57=7(mod 10. Recíprocamente, si resolvemos por el teorema chino estas dos condiciones nos daría como solución 9*9*7 + 10*1*3 = 597, que reducido a módulo 90 se convierte en 57.
Como las operaciones de suma y producto son compatibles con la relación de congruencia, a veces nos puede convenir sustituir números grandes por sus coordenadas, operar con ellas y después reconstruir los números. En Informática, si una unidad aritmética posee sus registros limitados, puede ser la única forma de operar.
Dígitos de control
Los dígitos de control se introducen en números grandes para verificar la corrección de su escritura. Los más populares son los de las cuentas bancarias, que tienen la forma EEEE OOOO CD NNNN NNNN, en la que EEEE representa a la entidad, OOOO a la oficina, CD son los dígitos de control y NN... la cuenta de referencia. Tanto C como D se calculan mediante congruencias módulo 11 a partir del resto de dígitos. En concreto, C proviene de una suma ponderada de los EEEE y OOOO y D procede del número de cuenta.
DNI
La letra del NIF se obtiene a partir del número del DNI hallándole su resto módulo 23 y usando después una tabla de equivalencia:
| Resto | 0 | 1 | 2 | ... |
| Letra | T | R | W | ... |
Funciones hash
Están basadas en las congruencias, y se usan para asignar posiciones de memoria de un ordenador a partir del número clave de un registro en una base de datos. Por ejemplo, si un alumno tiene una clave de seis dígitos, como 344 231, y sólo tenemos 512 posiciones de memoria para almacenar las claves, se utiliza la función de tipo hash (direccionamiento calculado)
f(344231) = 344231 mod 512
El problema de esto reside en que dos claves pueden ser asignadas a una misma posición. Diremos que se ha producido una colisión y a las claves se les llama sinónimas. Existen técnicas informáticas para resolverlo.