Las congruencias fueron introducidas formalmente por K. F. Gauss en su obra
Disquisitiones Arithmeticae para estudiar problemas aritméticos relacionados con la divisibilidad, aunque posteriormente se han aplicado a muchos de los problemas de la teoría de números.
Sean a y b números enteros y m>0 un número natural. Diremos que a y b son congruentes modulo m si m divide a a-b, y lo designaremos como
a=b (mod m).
Por ejemplo, los números que son congruentes a 0 módulo m son exactamente los múltiplos de m. La congruencia es una relación de equivalencia, puesto que verifica las propiedades reflexiva
a=a (mod m),simétricaa=b (mod m) si y solo si b=a (mod m),y transitivaa=b (mod m) y b=c (mod m), entonces a=c (mod m),como se puede comprobar fácilmente.
Así podemos agrupar los números enteros en familias disjuntas formadas por los números que son congruentes módulo m; obtenemos exactamente m familias, llamadas las clases de congruencia de m: son las familias de números congruentes con i módulo m variando i entre 0 y m-1.
Por ejemplo, las clases de congruencia módulo 2 son exactamente dos familias, la de los números pares y la de los números impares.
De la misma forma, hay exactamente 3 clases de congruencia módulo 3, formados por los números múltiplos de 3, los números múltiplos de 3 mas 1 y los números múltiplos de 3 mas 2 (o menos 1).
Designaremos por Z/mZ (zeta módulo m) las clases de congruencia módulo m; tenemos así, por ejemplo, que
Z/3Z={ 0, 1, 2 }.
Las propiedades más importantes de las congruencias es que respetan la suma y la multiplicación de números enteros:
Si a=b (mod m) y c=d (mod m), entonces a+c=b+d (mod m)
Si a=b (mod m) y c=d (mod m), entonces ac=bd (mod m)
