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

Примеры.

1. 
   Решим сравнение:
   

f (х) = х³ — 3 0 (mod 6). (2)
Надо подставить вместо х числа 0, 1, 2, 3, 4, 5,6. f (0) =-3, f (1) = -2, f (2) = 5, f(3) = 24, f(4) = 61, f(5) = 122. Только f(3) = 24 делится на 6. Значит, решением сравнения (2) является класс вычетов = {... -9, -3, 3, 9 ...}.
Разумеется, вместо чисел 0, 1,2, 3, 4, 5 можно было подставить числа, образующие иную полную систему вычетов по модулю 6, например числа
-2, -1,0, 1,2, 3.
Существуют сравнения, совсем не имеющие решений.

2. 
   Решим сравнение:
   

х⁴ + 2х — 1 0 (mod 7).
Составим полную систему абсолютно наименьших вычетов
0, 1, 2, 3, -3, -2, -1 по модулю 7. Ни один из вычетов данной системы не удовлетворяет данному сравнению. Следовательно, сравнение решений не имеет.
С теоретической точки зрения задача решения сравнений вида / (х) г= 0 (mod т) очень проста: мы просто ищем решения в конеч­ном множестве классов (т классов) по модулю т, что достигается, как мы уже установили, путем конечного числа испытаний выче­тов некоторой полной системы вычетов по модулю т. Однако на практике указанный прием испытания вычетов при больших мо­дулях оказывается затруднительнымдак как приводит к большому количеству испытаний. Например, для решения сравнения 19х⁸+ + 13х² — 2х + 17 Е55 0 (mod 625), следуя указанному приему ре­шения сравнений, надо проверить 625 вычетов.
Естественно возникает вопрос: нельзя ли упростить работу и свести ее к выполнению меньшего числа операции? Оказывается, можно. Существуют способы, позволяющие найти число решений сравнения, а в ряде случаев и найти все решения значительно быстрее.