Diccionario de congruencias

Diremos que a y b (números enteros) son congruentes módulo n (natural), si la diferencia b-a es un múltiplo de n. Representaremos la relación de congruencia como a=b (mod n).

La relación de congruencia es reflexiva, simétrica y transitiva, y por tanto da lugar a clases de equivalencia, llamadas también residuales.

Congruencias famosas

Congruencia de Fermat:

A^p-1=1_{(mod
p)} si p es primo.

Congruencia de Euler:

A^f(n)=1_{(mod n)} donde n no ha de ser necesariamente primo y f(n) es el indicador de Euler de dicho número.

Congruencia de Wilson:

(p-1)!+1=0_{(mod p)}con p primo.

Criterio de Congruencia

Criterio de congruencia

Dos números enteros a y b son congruentes módulo n, si y sólo si la diferencia b-a es un múltiplo de n

Chino

Teorema chino de los restos

Si A₁, A₂, …A_n son números primos entre sí dos a dos y a₁, a₂, a₃,…a_n, enteros cualesquiera, existe un número entero N que cumple N=a_{i (mod} A_i) para todo i entre 1 y n.

Para calcular ese número llamemos H al producto de todas las A_i y sea A’_i = H/A_i.

Se buscan unas m_i tales que m_i.A’_i=1 (mod A_i) y entonces la solución será:

N = S A_i.m_i.a_i

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’₁=9 ; A’₂=10 ; m₁=9 ; m₂=10 y por último:

N=9.7.9+10.3.10= 867

Ecuación

Ecuación de congruencias

Es toda ecuación definida sobre el anillo de las clases de restos Z/mZ

Euler

Indicador de Euler

Es una función f(n) que indica la cantidad de números inferiores a n y primos con él.

Si n es primo, su indicador será n-1

Una fórmula para esta función es

f(n)=n(1-1/p₁)(1-1/p₂)(1-1/p₃)... siendo p₁ p₂ p₃ los factores primos de n

Así, f(7) = 6, f(8) = 3 porque sólo son primos con él 3, 5 y 7.

Criterio de Euler

Si p es un número primo impar, y a es coprimo con p, entonces si

a^(p-1)/2 = 1 (mod p)

será a resto cuadrático respecto a p, y no lo será si

a^(p-1)/2 = -1 (mod p)

Fermat

Teoremas de Fermat

Teorema núm. 1 (pequeño teorema): Si p positivo es primo, entonces para todo n extraño con p se cumple que n^p =n (mod p)

Es equivalente afirmar que

Teorema núm. 2

Si p es primo y a es primo con p se cumple que a^p-1 = 1(mod p)

Fue generalizado por Euler así: Si a y n son extraños, se cumple que a^f(n) =1 (mod n), siendo f(n) el indicador de n

Gausiano

Gausiano de un número respecto a un módulo.

Es el mínimo exponente al que hay que elevar ese número para que produzca resto 1 al dividirlo entre el módulo. Por ejemplo, el gausiano de 3 respecto a 4 es 2, porque 3²=1 (mod 4)

Incongruente

Números incongruentes

Varios números son incongruentes módulo m, cuando dan todos restos distintos al dividirlos entre m.

Indicador de Euler

Ver Euler

Indice modular

Si n es una raíz primitiva respecto a un módulo primo p, diremos que el número a es índice modular de otro número b respecto a la base p, cuando n^a=b (mod p)

Inversible

Número inversible

Un número es inversible si posee inverso para una operación determinada

Inverso

Inverso de un número natural en Z/mZ

Dos números naturales a y b son inversos respecto al módulo m, si se cumple que a.b=1 (mod m)

Ley de reciprocidad cuadrática (ya descubierta por Legendre)

Si p y q son primos impares se cumple que el sistema de ecuaciones x² = q (mod p) y x² = p (mod q) tiene solución siempre, excepto si tanto p como q tienen la forma 4n+3, en cuyo caso, una tiene solución y la otra no.

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 a^g = b. A ese número g le llamaremos logaritmo discreto o índice de b con base a.

Módulo

Módulo en una congruencia

Es el número m que tiene el papel de divisor en la definición de congruencia

Prueba

Prueba del 9

Consiste en sustituir cada número en una operación por su resto al dividirlo entre 9 y someter los restos a las mismas operaciones para ver si son congruentes respecto a 9. El resto se calcula fácilmente sumando las cifras del número y restando 9 cuando sea posible. Por ejemplo:

Comprobar mediante restos respecto a 9 la corrección de esta operación:
568*899+23 = 510655
Pasando a restos: 1*8 + 5 = 13 que es congruente con 4, resto del resultado.

Pseudoaleatorio

Números naturales pseudoaleatorios

Son sucesiones de números, procedentes de fórmulas, que sin embargo parecen haber sido generados al azar. Para ello usan las propiedades de las congruencias.

Raíz

Raíz digital de un número entero positivo (en base 10)

La raíz digital de un número entero positivo es el dígito, entre 0 y 10, que resulta al sumar las cifras de su expresión decimal, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de una cifra, al que llamaremos raíz digital del número. Por ejemplo, la raíz digital del número 23451 es 6 , porque 2+3+4+5+1 = 15 y sumando las cifras del 15 resulta 6.

Se obtiene el mismo resultado calculando el resto módulo 9 de ese número, pero en caso de ser 0 se sustituye por 9.

Raíz primitiva respecto a un módulo primo

Un número n constituye una raíz primitiva respecto a un módulo primo p, cuando el gausiano de n respecto a p es exactamente p-1

Relación

Relación de congruencia

Dos números están relacionados por una congruencia cuando son congruentes respecto a un módulo dado. Esta relación es reflexiva, simétrica y transitiva y produce, por tanto, clases de equivalencia, llamadas también clases de restos o residuales.

Residual

Ver Clases

Resto

Resto potencial

Llamaremos restos potenciales de un número natural z respecto a un módulo m a los restos de dividir las potencias de z entre m. Por ejemplo, los restos potenciales del número 7 respecto a 5 son:

r₀=1 r₁=2 r₂=4 r₃=3 ...

Resto cuadrático

Un elemento a de unas clases de restos es resto cuadrático cuando es resto potencial de algún cuadrado, es decir, que existe un n tal que n² = a (mod m). En caso contrario diremos que a es no resto cuadrático.

Sistema

Sistema de ecuaciones en congruencias

Es un conjunto de ecuaciones de congruencia con soluciones comunes.

Ver el Teorema Chino

Sistema de números incongruentes

Es un conjunto de números naturales cuyos restos respecto a un módulo dado son todos diferentes.

Por ejemplo: los números 13, 24 y 31 forman un sistema de números incongruentes respecto al 5.

Sistema completo de números incongruentes

Un sistema de números incongruentes se llama completo cuando sus restos completan todo el conjunto de los posibles respecto a un módulo.

Por ejemplo: El sistema 2,7,8,13 es completo respecto a 4, porque produce los restos 2,3,0 y 1.

Teorema

Ver Teoremas Chino, Fermat,

Wilson

Teorema de Wilson

Para que n divida a (n-1)!+1 es necesario y suficiente que n sea primo.

Por tanto, para p>0 primo tendremos que (p-1)! Es congruente con –1 módulo p