Kongruence modulo m je relace, kterou označujeme, že dvě čísla a a b mají stejný zbytek po celočíselném dělení číslem m. Jinými slovy platí, že .

Zápis:

a ≡ b mod(m), čteme a je kongruentní b modulo m.

Příklady:

Jak jste si asi všimli, tak množství kongruencí modulo m je nekonečné, proto se obvykle používá nejmenší nezáporné reziduum, což je nejmenší zbytek po dělení, který je ještě nezáporný.