Решение сравнений и их приложения

Определение 1. Пусть f(х) = а₀х^п + ... + а_п , φ(х)=bоХ^к + ... + b_k — многочлены с целыми коэффициентами а₀,…,а_п , bо,…,b_k . Решить сравнение f (х) φ(x) (mod m) — значит найти все целые числа х, при подстановке которых в мно­гочлены f(х) и φ(х) получаются целые числа, разность которых делится на m. Если f(с) (с) (mod m), то говорят, что целое число с удовлетворяет сравнению f (х) φ(x) (mod m), или, ина­че, является корнем этого сравнения.
Теорема 1.
Если число с удовлетворяет сравнению
f (х) φ (х) (mod m), (1)
mo и любое число с₁ такое, что с с₁ (mod m), удовлетворяет тому же сравнению.
Доказательство.
Так как с удовлетворяет сравнению (1), то f(с) φ (с) (mod m), то есть f(с) — φ (с) 0 (mod m). Но так как с с₁ (mod m), то по свойству 11 сравнений и f(с₁) φ (с₁) (mod m). Теорема доказана.
Из доказанной теоремы вытекает, что если целое число с удов­летворяет сравнению f(x) 0 (mod m), то и все числа из содержа­щего с класса вычетов по модулю т удовлетворяют тому же срав­нению. Поэтому задача о решении сравнений может быть поставле­на иначе:
Определение . Решить сравнение:
f (х) φ (х) (mod m),
где f(х) и φ(х) — многочлены с целыми коэффициентами— значит найти все классы вычетов по модулю m, любое число из которых удовлетворяет сравнению (1) (то есть при подстановке в (1) любого числа из этих классов вычетов получаются числа, сравнимые по модулю т).
Из определения вытекает, что любое сравнение вида (1) мож­но решить, сделав т проб, а именно, подставив в f(х) и φ (х) вместо х по очереди все числа из полной системы вычетов по модулю т (например, числа
0, 1,…, т-1). После этого надо вычислить значения f(с) и φ(с) и отобрать те, для которых f (с) — φ (с) де­лится на т.