Теория сравнений (стр. 9 из 12)

.

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

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

Из этой теоремы непосредственно вытекает следующая.

Теорема 3. Сравнение по простому модулю

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

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

многочлен с целыми коэффициентами степени . При делении на ), частное и остаток будут также многочленами с целыми коэффициентами:

,

где степень

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

Пример 2. Сравнение

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

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

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

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

.

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

многочлены с целыми коэффициентами: , и все коэффициенты делятся на простое число , то любое решение сравнения

(3.17)

является решением, по крайней мере, одного из сравнений:

(3.18)

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

решение сравнения (3.17), т.е. . Поскольку все коэффициенты делятся на , будем также иметь , поэтому

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

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

Пример 3. В сравнении

левую часть можно представить в виде , и мы находим все решения этого сравнения, решая сравнения: , , т.е. и . Все эти четыре класса удовлетворяют нашему сравнению.

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

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

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

,

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

по простому модулю с коэффициентом при старшем члене, не делящимся на , может иметь не больше чем решений.

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

. Действительно, в этом случае мы имеем сравнение 1-й степени: , где , т.е. , а такое сравнение имеет в точности одно решение. Применим теперь для доказательства теоремы метод полной математической индукции.

Предположим, что утверждение теоремы верно для всех многочленов (

) – й степени со старшими коэффициентами, не делящимися на простой модуль . Возьмем теперь произвольный многочлен – й степени:

,

где

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

(3.19)

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

.

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

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

.

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

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

Поскольку

удовлетворяет сравнению (3.19), , то все решения (3,19) находятся среди решений сравнений и , удовлетворяя либо одному из них, либо обоим.

Сравнение

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