Определение 1. Пусть f (x) = a 0 xn + a 1 xn- 1+…+ an Î Z [ x ], a 0 T 0(mod m). Сравнением с неизвестной m-й степени по модулю m называется сравнение вида
f (x) º 0(mod m). (1)
Говорят, что целое число x 0 удовлетворяет сравнению (1), если при подстановке в сравнение (1) вместо x числа x 0 получаем верное числовое сравнение.
Лемма 1. Если число x 0 удовлетворяет сравнению (1), то и любое число x 1Î` x 0, удовлетворяет сравнению (1).
Доказательство. Пусть число x 0 удовлетворяет сравнению (1) и x 1Î` x 0. Тогда
x 1 º x 0 (mod m) и f (x 0) º 0(mod m). Тогда по свойству сравнений
f (x 1) º f (x 0) º0(mod m).ÿ
Определение 2. Решением сравнения (1) по модулю m называется класс вычетов по модулю m, все числа которого удовлетворяют сравнению (1).
Так как имеется всего m классов по модулю m, то любое сравнение по модулю m можно решить не более чем за испытаний, следующим способом.
Выписать некоторую полную систему вычетов по модулю m, например, 0, 1, 2, …, m -1, и проверить какие числа этой системы удовлетворяют сравнению. Соответствующие классы вычетов по модулю m дают решения сравнения.
Пример 1. Решить сравнение 2 x 5 + 3 x 3 - 4 x 2 + x - 2(mod 7).
Запишем полную систему вычетов по модулю 7: -3, -2, -1, 0, 1, 2, 3. Проверим, какие числа из ее удовлетворяют нашему сравнению (проверку можно вести по схеме Горнера, а вычисления проводить по модулю 7). В
| -4 | -2 | ||||||
| -3 -2 -1 | -1 | Да Да Да |
Сравнение имеет три решения `1,`3, `4 (mod 7).
Рассмотрим сравнение 1-й степени по модулю
axº b (mod m). (2)
Теорема 1. Пусть НОД(a, m) = d. Тогда справедливы утверждения:
1) если d F b, то сравнение (2) не имеет решений;
2) если (a, m) = 1, то сравнение (2) имеет единственное решении, которое находится по формуле:
; (3)
3) если d | b, то сравнение (2) имеет d решений по модулю m, которые находятся по формулам:
(4)
где x 0 - решение сравнения
(5)
Доказательство. Пусть НОД(a, m) = d.
1. Пусть d F b. Покажем, что сравнение(2) не имеет решений. Допустим противное, что сравнение (2) имеет решение и пусть число x 1- удовлетворяющее сравнению (2). Тогда имеем
ax 1 º b (mod m).
Отсюда по определениям сравнимости и делимости чисел получаем равенство
ax 1 = b + mq.
Так как d | a, d | m, то отсюда следует, что d | b. Последнее противоречит предположения.
2. Пусть (a, m) = 1. Докажем, что в этом случае решения сравнения(3) находятся по формуле (3). Действительно, пусть число x 1- удовлетворяющее сравнению (2). Тогда имеем сравнение (3). Умножаем обе части сравнения (3) на число
получим
. (6)
Так как (a, m) = 1, то по теореме Эйлера
.
Следовательно, из формулы (6) получаем
,
т.е. находится по формуле (3).
Покажем теперь, что число, найденное по формуле (3) удовлетворяет сравнению (2):
.
3. Пусть d | b. Так как d | b, d | a, d | m, то разделим обе части сравнения (2) и модуль на число d, и получим сравнение (5), в котором 
. Тогда сравнение (5) имеет единственное решение ` x 0 mod(m/d).
Докажем, что класс ` x 0 mod(m/d) совпадает с объединением d различных классов (4).
Пусть целое число x Î` x 0 mod(m/d). Тогда x = x 0 + (m/d) q. Разделим число q на d с остатком q = td + k, k Î {0, 1, …, d -1}. Тогда число
x = x 0 + (m/d)(td + k) = x 0 + (m/d) k + mt
принадлежит одному из классов (4)
Обратно пусть целое число x принадлежит одному из классов (4),
.
Тогда
x = x 0 + (m/d) k + mt = x 0 + (m/d)(k +dt) Î x 0 mod(m/d).
Наконец, так как классы (4) принадлежат попарно различным остаткам по модулю m/d, то они попарно различны. Поэтому сравнение (2) имеет d решений по модулю m. ÿ
Сравнение (2) для малых модулей m можно решить методом подбора или используя простейшие свойства сравнений.
Пример 2. Решить сравнение 5 x º 6(mod 7).
Умножим обе части сравнения на число 3, взаимно простое с модулем получим равносильное сравнение
15 x º 18(mod 7).
Так как 15 º 1(mod 7), 18 º 4(mod 7), то находим
x º 4(mod 7), `4 mod 7.
Для сравнительно небольших m сравнение можно решить по формуле (3) используя бинарный способ возведения в большую степень.
Пример 3. Решить сравнение 122 x º 142(mod 212).
Так как НОД(122, 212) = 2, и 2|142, то данное сравнение имеет 2 решения по модулю 142. Разделимо, обе части сравнения и модуль на число 2 и получим равносильное сравнение:
61 x º 71(mod 106).
Решаем последнее сравнение по формуле (3). Так как 106 = 2×53, то j(106)=1×52 = 52. Тогда по формуле (3) находим:
Отсюда по формулам (5) находим решения исходного сравнения 
.
Третий способ наиболее быстрый и основан на алгоритме деления с остатком. Решаем сравнение (2) в случае (a, m) = 1. Для этого разложим рациональную несократимую дробь m/a в цепную дробь: m/a = [ a 1, a 2,…, ak,]. Тогда по свойству подходящих дробей будем иметь
mQk -1 – aPk -1 = (-1) k.
Отсюда находим
aPk -1(-1) k -1 º 1(mod m)
Тогда, умножая обе части сравнения (2) на
Умножим обе части сравнения (2) на Pk -1(-1) k -1 получим:
xº b Pk -1(-1) k -1(mod m). (7)
Пример 4. Решить сравнение 61 x º 71(mod 106).
Разлагаем число 106/61 в цепную дробь:
106 = 61×1 + 45,
61 = 45×1 + 16,
45 = 16×2+13
16=13×1+3
13 = 3×4+1
3=1×3
Итак, получаем 106/61 = [2, 15, 4]. Находим числители подходящих дробей
| i | |||||||
| ai | - | ||||||
| Pi |
Тогда по формуле (7) получаем xº 71×33(-1)6-1 º 95 (mod m).