
.
Пользуясь той же теоремой Ферма, получаем, что если

удовлетворяет сравнению (3,16), то
, и, таким образом, сравнения (3,15) и (3,16) эквивалентны.
Из этой теоремы непосредственно вытекает следующая.
Теорема 3. Сравнение по простому модулю

, степень которого больше, чем этот модуль или равна ему, может быть заменено эквивалентным сравнением степени, меньшей

.
Доказательство. Пусть

многочлен с целыми коэффициентами степени

. При делении

на

), частное

и остаток

будут также многочленами с целыми коэффициентами:

,
где степень

меньше степени

, т.е. меньше, чем

. Согласно предыдущей теореме, сравнения

и

эквивалентны.
Пример 2. Сравнение

заменить эквивалентным сравнением степени, меньшей чем 7.
Решение. Мы получим эквивалентное сравнение, если заменим

на

,

на

,

на

. Таким образом, заданное сравнение эквивалентно сравнению

т.е. сравнению

.
Теорема 4. Если

многочлены с целыми коэффициентами:

, и все коэффициенты

делятся на простое число

, то любое решение сравнения
является решением, по крайней мере, одного из сравнений:
Доказательство. Пусть

решение сравнения (3.17), т.е.

. Поскольку все коэффициенты

делятся на

, будем также иметь

, поэтому

Из сравнимости произведения

с нулем по модулю

следует, что по крайней мере один из этих множителей сравним с нулем по этому модулю, т.е.

решение по крайней мере одного из сравнений (3.18).
Пример 3. В сравнении

левую часть можно представить в виде

, и мы находим все решения этого сравнения, решая сравнения:

,

, т.е.

и

. Все эти четыре класса удовлетворяют нашему сравнению.
Для составных модулей эта теорема неверна. Например, сравнению

удовлетворяет класс

, не являющийся решением ни одного из сравнений:

,

Теорема 5. Сравнение степени

по простому модулю

с коэффициентом при старшем члене, не делящимся на

, может иметь не больше чем

решений.
Доказательство. Утверждение теоремы верно при

. Действительно, в этом случае мы имеем сравнение 1-й степени:

, где

, т.е.

, а такое сравнение имеет в точности одно решение. Применим теперь для доказательства теоремы метод полной математической индукции.
Предположим, что утверждение теоремы верно для всех многочленов (

) – й степени со старшими коэффициентами, не делящимися на простой модуль

. Возьмем теперь произвольный многочлен – й степени:

,
где

, и рассмотрим сравнение
Если это сравнение не имеет ни одного решения, то число решений меньше чем

.
Если же это сравнение имеет решения, то возьмем любое число

, удовлетворяющее ему, и разделим

на

. Согласно теореме Безу будем иметь:

.
Коэффициенты многочлена

-й степени

могут быть найдены по схеме Горнера и представляют собой целые числа, причем

.
Поскольку

удовлетворяет сравнению (3.19),

, то все решения (3,19) находятся среди решений сравнений

и

, удовлетворяя либо одному из них, либо обоим.
Сравнение

имеет одно решение, а сравнение

представляет собой сравнение
(
) – й степени по простому модулю с коэффициентом при старшем члене
, не делящемся на

, и, по предположению, может иметь не больше чем

решений. Таким образом, сравнение (5) имеет не больше, чем

, т.е. не больше чем

решений.