Решение линейных сравнений в целых числах
Рассмотрим сравнение вида
ax º b (mod m), (1.7.1)
где a, b Î Z, m Î N, х – искомое значение в Z.
1. Пусть (a, m) = 1. Тогда (1.7.1) имеет в качестве множества решений 
– единственный класс вычетов по модулю m. По теореме 1.7.1 
– обратимый класс в Z/mZ. 
– единственный обратный класс к . В Z/mZ сравнение (1.7.1) соответствует уравнению 
. Умножим обе его части на , получим 
. 
= {x + mq | q Î Z} – множество решений (1.7.1). можно найти из соотношения Безу для 1 и чисел a и m, или согласно следствию из теоремы 1.7.3 
2. Пусть (a, m) = d > 1 и 
, тогда (1.7.1) не имеет решений в Z, поскольку не выполняется свойство 6 делимости целых чисел: ax = b + mq, q Î Z, d | a, d | m, но .
3. Пусть (a, m) = d > 1 и d | b. Тогда разделим обе части (1.7.1) и m на d согласно свойству 5 сравнений. Получим сравнение
a1x º b1 (mod m1), (1.7.2)
где a1 = a/d, b1 = b/d, m1 = m/d, и (a1, m1) = 1 по свойству 1 взаимно простых чисел. (1.7.2) имеет в качестве множества решений единственный класс вычетов 
по модулю m1 согласно случаю 1. Числа из = {x0 + m1q | q Î Z} являются решениями (1.7.1), так как a(x0 + m1q) = da1x0 + ma1q º db1 + dm1t0 º b (mod m) для " q Î Z и фиксированного t0 Î Z. Какие еще возможны решения (1.7.1)? Пусть 
– решение (1.7.1), тогда 
. Это возможно тогда, когда 
Û m | ay Û m1 | a1y Þ m1 | y по свойству 2 взаимно простых чисел, значит, 
. С другой стороны, для таких значений y любое 
является решением сравнения (1.7.1). Итак, по модулю m 
– все множества решений (1.7.1).