Definición: 

Sean a y b enteros y n un entero positivo. Si a - b es divisible entre n, se dice que a es congruente con b módulo n, y se escribe

a = b (mod n)

Obviamente, a = b (mod n) si y sólo si existe k entero tal que a = b + kn.

Ejemplos:

-9 = 31 (mod 10)

16 = 30 (mod 7)

Propiedades fundamentales de las congruencias:

1) La congruencia módulo n es una relación de equivalencia en los enteros, es decir:

i) a = a (mod n) para todo a entero.

ii) Si a = b (mod n) entonces b = a (mod n) para todos a y b enteros.

iii) Si  a = b (mod n) y b = c (mod n) entonces a = c (mod n) para todos a, b y c enteros.

2) Si a = b (mod n) y c = d (mod n) entonces

a + c = b + d (mod n)     y     ac = bd (mod n)

3) Si (a,n) = d     y     ab = ac (mod n) entonces

b = c (mod n/d)

((a,n) es el máximo común divisor de a y n)

Demostración de 3):

Existe un k entero tal que ab = ac + kn        (1)

Sean A=a/d, N=n/d. Se tiene entonces que (A,N)=1

Dividiendo (1) entre d, se obtiene:

A(b - c) = kN            (2)

 por lo que A divide a kN. Como (A,N)=1, es necesario que A divida a k, de donde hay un entero R tal que k=AR. Sustituyendo en (2):

b - c = RN

lo que implica que b = c (mod N)

Sistema completo de restos

Cada entero es congruente módulo n con exactamente uno de los n números 0, 1, 2, ... n -1.

Demostración:

Sea z un entero cualquiera. Dividiéndolo entre n, se obtiene:

z = qn + r,    0 <= r < n, de donde se deduce que z es congruente módulo n a r, que es un número entre 0 y n-1.

Supongamos ahora que 0 <= r1 <  r2 < n y que z = r1 (mod n) y z = r2 (mod n)

Se cumple que

r1 =  r2 (mod n) por lo que n divide a r2 - r1, pero

0 < r2 - r1 <= n - 1 < n, lo que es una contradicción.

Definición: 

Un conjunto de n enteros z₁, z₂, ..., z_n, se llama sistema completo de restos módulo n si cada entero es congruente módulo n con exactamente uno de los zetas.

El hecho de que los números 0, 1, 2, ..., n - 1 formen un sistema completo de restos módulo n implica que cualquier combinación de sumas, diferencias y productos de esos números es congruente módulo n con exactamente un miembro del sistema. Esto es la base de la idea de la aritmética modular. 

ECUACIONES LINEALES EN CONGRUENCIAS

Una ecuación de la forma

a₁x₁ + a₂x₂ + ... + a_kx_k = b (mod n)         (E)

es una ecuación lineal en congruencia en k variables. Su solución es un conjunto de enteros que satisfacen la ecuación. (E) es equivalente a la ecuación diofántica 

a₁x₁ + a₂x₂ + ... + a_kx_k  - nx_{k + 1} = b        (E')

con k + 1 incógnitas, la cual o tiene infinitas soluciones o no tiene ninguna. En el caso en que k = 1 es fácil hallar la solución de (E') si existe.

Teorema

La ecuación 

ax = b (mod n)     (E1) 

tiene soluciones si y sólo si d divide a b, siendo d = (a,n). En este caso la solución es única módulo n/d. 

Demostración:

Si x = t es una solución de (E1), entonces existe un entero u tal que 

at = b + nu

o sea la ecuación

ax - ny = b  (E2)

tiene una solución. Si x = t, y = u es una solución de (E2), entonces

at = at - nu = b (mod n), 

por lo que (E1) tiene una solución. Por lo tanto (E1) tiene solución si y sólo si (E2) las tiene y toda solución para x en (E2) da una solución para x en (E1). (E2) tiene soluciones si y sólo si d divide a b, igualmente que (E1). Supongamos que (E2) tiene la solución x = u, y = t. De aquí, toda solución de (E2) es de la forma 

x = u + z(n/d)      y = t + z(a/d)

Siendo z un entero. Entonces toda solución de (E1) es de la forma

x = u + z(n/d).

Como

u + z(n/d) = u (mod n/d)

Todas las soluciones de (E1) son congruentes con u módulo n/d.

Teorema

Si (m,n) = 1, entonces las ecuaciones 

x = a (mod m)

x = b (mod n)

tienen una única solución módulo mn.

Demostración:

Un entero x satisface la primera ecuación si y sólo si existe un entero t tal que 

x = a + mt    (E3)

Éste satisface la segunda ecuación si y sólo si 

mt = b - a (mod n)    (E4)

Como (m,n) = 1 la última ecuación tiene una solución única módulo n, digamos 

t = c (mod n) 

Este t satisface (E4) si y sólo si hay un entero k tal que 

t = c + nk.

Sustituyendo en (E3) encontramos que x es una solución común de las dos ecuaciones originales si y sólo si 

x = a + m(c + nk) = (a + mc) + mnk

por lo que las dos ecuaciones tienen soluciones comunes, una de las cuales es a + mc, y todas las soluciones son congruentes a ésta módulo mn.

Teorema Chino de los Restos

Sean m₁, ..., m_k enteros positivos primos entre sí dos a dos. . Entonces las k ecuaciones

x = a₁ (mod m₁), ... , x = a_k (mod m_k)

tienen una única solución módulo m₁m₂...m_k

Para demostrarlo, se utiliza el teorema anterior k - 1 veces. 

Teorema

Si (cf - de) = 1, entonces las ecuaciones

cx + ey = a (mod n)

dx + fy = b (mod n)

tienen una única solución módulo n

La demostración es un poco engorrosa y no la daré aquí. La solución se puede encontrar haciendo combinaciones lineales de las dos ecuaciones.