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

Согласно принципу математической индукции справедливость теоремы доказана.

Пример 4.

удовлетворяет сравнению Найти все решения этого сравнения.

Очевидно, что вместе с классом

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

Ответ.

.

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

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

Теорема 6. Если сравнение степени

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

Доказательство. Возьмем любое простое число

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

Возьмем любое сравнение степени

:

(3.20)

имеющее больше чем

решений. В таком сравнении делится на , а тогда сравнение

(3.21)

эквивалентное сравнению (3.20), также имеет больше чем

решений.

В сравнении (3.21), степень которого меньше чем

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

Теорема 7. Пусть

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

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

, где и многочлены с целыми коэффициентами, причем степень меньше чем .

1) Докажем достаточность условия. Пусть коэффициенты

делятся на .

Обозначим через

и соответственно число решений сравнений

	(3.22)
	(3.23)

Сравнение

по теореме Ферма имеет решений. Каждое из этих решений является решением хотя бы одного из сравнений: (3.22) или (3.23), т.е.

Сравнение (3.23) степени

имеет коэффициент при старшем члене, равный единице, так что и, следовательно,

.

Поскольку при этом

, получаем , т.е. из делимости коэффициентов на следует, что число решений сравнения (3.22) равно .

2) Докажем необходимость условия. Пусть сравнение (3.22) имеет

решений. Если решение сравнения (3.22), то и вместе с тем, поскольку , то , а, следовательно, согласно теореме Ферма, , так что

Таким образом, каждое из

решений сравнения (3.22) является решением сравнения , степень которого меньше чем . Следовательно, все коэффициенты делятся на .