Сравнения по простому модулю с одним неизвестным
Переходя от сравнений 1-й степени к сравнениям более высоких степеней, целесообразно сначала рассмотреть тот случай, когда модуль – простое число. В этом случае имеется ряд весьма важных теорем, которые, вообще говоря, неверны для составных модулей. Вместе с тем теория сравнений по простому модулю является основой, на которой строится изучение сравнений по составному модулю. Во всей этой главе буквой будем обозначать модуль, представляющий собой простое число. Теорема 1.Если , то сравнение может быть заменено эквивалентным сравнением с коэффициентом при старшем члене, равном единице. Доказательство. Рассмотрим сравнение 1-й степени ; поскольку то и сравнение имеет решение. Найдем число , удовлетворяющее этому сравнению, т.е. такое, что . Тогда сравнение эквивалентно сравнению , а следовательно, сравнению , где . Пример 1. Заменить сравнение эквивалентным сравнением с коэффициентом при старшем члене, равным 1. Решаем сравнение и находим . Данное нам сравнение эквивалентно сравнению т.е. сравнению . Теорема 2. Если и многочлены с целыми коэффициентами, то сравнения по простому модулю
эквивалентны. Доказательство. Пусть удовлетворяет сравнению (3,15), т.е. . Поскольку при любом согласно теореме Ферма , то . Пользуясь той же теоремой Ферма, получаем, что если удовлетворяет сравнению (3,16), то , и, таким образом, сравнения (3,15) и (3,16) эквивалентны. Из этой теоремы непосредственно вытекает следующая. Теорема 3. Сравнение по простому модулю , степень которого больше, чем этот модуль или равна ему, может быть заменено эквивалентным сравнением степени, меньшей . Доказательство. Пусть многочлен с целыми коэффициентами степени . При делении на ), частное и остаток будут также многочленами с целыми коэффициентами: , где степень меньше степени , т.е. меньше, чем . Согласно предыдущей теореме, сравнения и эквивалентны. Пример 2. Сравнение заменить эквивалентным сравнением степени, меньшей чем 7. Решение. Мы получим эквивалентное сравнение, если заменим на , на , на . Таким образом, заданное сравнение эквивалентно сравнению т.е. сравнению . Теорема 4.Если многочлены с целыми коэффициентами: , и все коэффициенты делятся на простое число , то любое решение сравнения
является решением, по крайней мере, одного из сравнений:
Доказательство. Пусть решение сравнения (3.17), т.е. . Поскольку все коэффициенты делятся на , будем также иметь , поэтому Из сравнимости произведения с нулем по модулю следует, что по крайней мере один из этих множителей сравним с нулем по этому модулю, т.е. решение по крайней мере одного из сравнений (3.18). Пример 3. В сравнении левую часть можно представить в виде , и мы находим все решения этого сравнения, решая сравнения: , , т.е. и . Все эти четыре класса удовлетворяют нашему сравнению. Для составных модулей эта теорема неверна. Например, сравнению удовлетворяет класс , не являющийся решением ни одного из сравнений: , Теорема 5.Сравнение степени по простому модулю с коэффициентом при старшем члене, не делящимся на , может иметь не больше чем решений. Доказательство. Утверждение теоремы верно при . Действительно, в этом случае мы имеем сравнение 1-й степени: , где , т.е. , а такое сравнение имеет в точности одно решение. Применим теперь для доказательства теоремы метод полной математической индукции. Предположим, что утверждение теоремы верно для всех многочленов ( ) – й степени со старшими коэффициентами, не делящимися на простой модуль . Возьмем теперь произвольный многочлен – й степени: , где , и рассмотрим сравнение
Если это сравнение не имеет ни одного решения, то число решений меньше чем . Если же это сравнение имеет решения, то возьмем любое число , удовлетворяющее ему, и разделим на . Согласно теореме Безу будем иметь: . Коэффициенты многочлена -й степени могут быть найдены по схеме Горнера и представляют собой целые числа, причем . Поскольку удовлетворяет сравнению (3.19), , то все решения (3,19) находятся среди решений сравнений и , удовлетворяя либо одному из них, либо обоим. Сравнение имеет одно решение, а сравнение представляет собой сравнение ( ) – й степени по простому модулю с коэффициентом при старшем члене , не делящемся на , и, по предположению, может иметь не больше чем решений. Таким образом, сравнение (5) имеет не больше, чем , т.е. не больше чем решений. Согласно принципу математической индукции справедливость теоремы доказана. Пример 4. удовлетворяет сравнению Найти все решения этого сравнения. Очевидно, что вместе с классом этому сравнению удовлетворяет и класс . Коэффициент при старшем члене не делится на простой модуль , поэтому сравнение не может иметь больше двух решений. Ответ. . Для составных модулей эта теорема неверна. Сравнение степени по составному модулю с коэффициентом при старшем члене, не делящемся на модуль или даже взаимно простом с модулем, может иметь больше чем решений. Например, сравнение имеет 4 решения: . Теорема 6.Если сравнение степени по простому модулю имеет больше чем решений, то все коэффициенты сравнения делятся на . Доказательство. Возьмем любое простое число . Если сравнение имеет больше чем одно решение, то , т.е. . Таким образом, при теорема верна. Предположим, что утверждение теоремы верно для многочленов степени, меньшей чем , т.е. предположим, что число решений сравнения степени, меньшей чем , может превосходить степень сравнения только тогда, когда все коэффициенты делятся на модуль . Возьмем любое сравнение степени :
имеющее больше чем решений. В таком сравнении делится на , а тогда сравнение
эквивалентное сравнению (3.20), также имеет больше чем решений. В сравнении (3.21), степень которого меньше чем , а число решений превосходит степень согласно предположению, все коэффициенты должны делиться на , т.е. . Поскольку уже раньше было установлено, что , утверждение теоремы верно для . Согласно принципу математической индукции справедливость теоремы доказана. Теорема 7.Пусть многочлен с целыми коэффициентами и свободным членом , где простое число, причем . Сравнение имеет решений тогда и только тогда, когда все коэффициенты остатка от деления на кратны . Доказательство. Пусть , где и многочлены с целыми коэффициентами, причем степень меньше чем . 1) Докажем достаточность условия. Пусть коэффициенты делятся на . Обозначим через и соответственно число решений сравнений
Сравнение по теореме Ферма имеет решений. Каждое из этих решений является решением хотя бы одного из сравнений: (3.22) или (3.23), т.е. Сравнение (3.23) степени имеет коэффициент при старшем члене, равный единице, так что и, следовательно, . Поскольку при этом , получаем , т.е. из делимости коэффициентов на следует, что число решений сравнения (3.22) равно . 2) Докажем необходимость условия. Пусть сравнение (3.22) имеет решений. Если решение сравнения (3.22), то и вместе с тем, поскольку , то , а, следовательно, согласно теореме Ферма, , так что Таким образом, каждое из решений сравнения (3.22) является решением сравнения , степень которого меньше чем . Следовательно, все коэффициенты делятся на . Пример 5. Сравнению удовлетворяют классы и . Имеет ли это сравнение еще одно решение? Делим на , находим: так что и, следовательно, это сравнение имеет три решения.
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (225)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |