Числа с одинаковым остатком деления на натуральное число 
называются сравнимыми по модулю . Факт сравнимости чисел 
и 
по модулю будем записывать 
.
В ряде приложений требуется решать уравнения вида ах 
b(c), называемые также сравнениями. Например, решением сравнения 3х 2(5), является х=4, а сравнение 3х 2(mod 6), решений не имеет.
Для поиска решения сравнения воспользуемся расширенным алгоритмом Евклида для чисел а и с. Пусть u и v — целые числа, удовлетворяющие уравнению au+vc=НОД(a,c). Если b не делится на НОД(a,c), то решения сравнения не существуют.
Если b делится на НОД(a,c), то решениями сравнения являются числа вида
x=bu/НОД(a,c)+ct/НОД(a,c) при любом целом t. Решения сравнения имеют период с, поэтому часто в качестве решения указывают только положительные числа, меньшие с. С учетом сделанного замечания, общее решение сравнения имеет вид x=bu/НОД(a,c)+ct/НОД(a,c), где t=0,1,…,НОД (a,c)-1. Когда НОД (a,c)=1, формула принимает простой вид х bu(c).
