El concepto de congruencia se le atribuye a Carl Gauss al proponer el símbolo ≡ para identificarlas en su «Disquisitiones Arithmeticae» de 1.801. Es una relación de equivalencia que permite clasificar a los números enteros en familias (conjuntos formados por cada número entero y todos sus congruentes), estas familias se denominan clases residuales módulo m.

Definición:
Tenemos dos enteros a y b, y otro entero positivo m.
a y b son congruentes módulo m, si el resto de a / m es igual al resto de b / m. Es decir a mod m = b mod m
La notación es a ≡ b (mód m), también encontramos a ≡ b (m)
Propiedades:
- Reflexiva: a ≡ b (mód m), para todo a ∈ Z.
- Simétrica: a ≡ b (mód m) ⇒ b ≡ a (mód m).
- Transitiva: a ≡ b (mód m) y b ≡ c (mód m) ⇒ a ≡ c (mód m).
Ejemplos:
- 18 ≡ 3 (mód 5)
- 66 ≡ 1 (mód 5)
- 1492 ≡ 78 ( mód 101)
- 3125 ≡ 1 (mod 11)
Una relación importante de la congruencia y la aritmética modular es con el Pequeño Teorema de Fermat y el Teorema Chino del Resto.