Теория сравнений
.
Пользуясь той же теоремой Ферма, получаем, что если удовлетворяет сравнению (3,16), то
, и, таким образом, сравнения (3,15) и (3,16) эквивалентны.
Из этой теоремы непосредственно вытекает следу
ющая.
Теорема 3. Сравнение по простому модулю , степень которого больше, чем этот модуль или равна ему, может быть заменено эквивалентным сравнением степени, меньшей
.
Доказательство. Пусть многочлен с целыми коэффициентами степени
. При делении
на
), частное
и остаток
будут также многочленами с целыми коэффициентами:
,
где степень меньше степени
, т.е. меньше, чем
. Согласно предыдущей теореме, сравнения
и
эквивалентны.
Пример 2. Сравнение заменить эквивалентным сравнением степени, меньшей чем 7.
Решение. Мы получим эквивалентное сравнение, если заменим на
,
на
,
на
. Таким образом, заданное сравнение эквивалентно сравнению
т.е. сравнению .
Теорема 4.Если многочлены с целыми коэффициентами:
, и все коэффициенты
делятся на простое число
, то любое решение сравнения
|
(3.17) |
является решением, по крайней мере, одного из сравнений:
|
(3.18) |
Доказательство. Пусть решение сравнения (3.17), т.е.
. Поскольку все коэффициенты
делятся на
, будем также иметь
, поэтому
Из сравнимости произведения с нулем по модулю
следует, что по крайней мере один из этих множителей сравним с нулем по этому модулю, т.е.
решение по крайней мере одного из сравнений (3.18).
Пример 3. В сравнении левую часть можно представить в виде
, и мы находим все решения этого сравнения, решая сравнения:
,
, т.е.
и
. Все эти четыре класса удовлетворяют нашему сравнению.
Для составных модулей эта теорема неверна. Например, сравнению
удовлетворяет класс , не являющийся решением ни одного из сравнений:
,
Теорема 5.Сравнение степени по простому модулю
с коэффициентом при старшем члене, не делящимся на
, может иметь не больше чем
решений.
Доказательство. Утверждение теоремы верно при . Действительно, в этом случае мы имеем сравнение 1-й степени:
, где
, т.е.
, а такое сравнение имеет в точности одно решение. Применим теперь для доказательства теоремы метод полной математической индукции.
Предположим, что утверждение теоремы верно для всех многочленов () – й степени со старшими коэффициентами, не делящимися на простой модуль
. Возьмем теперь произвольный многочлен – й степени:
,
где , и рассмотрим сравнение
|
(3.19) |
Другие рефераты на тему «Математика»:
Поиск рефератов
Последние рефераты раздела
- Анализ надёжности и резервирование технической системы
- Алгоритм решения Диофантовых уравнений
- Алгебраическое доказательство теоремы Пифагора
- Алгоритм муравья
- Векторная алгебра и аналитическая геометрия
- Зарождение и создание теории действительного числа
- Вероятностные процессы и математическая статистика в автоматизированных системах