Изложение теоретического материала иллюстрируется большим количеством примеров с подробными решениями
 Скачать 1.34 Mb.
|
3.4 Сравнения по простому модулю с одним неизвестнымПереходя от сравнений 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. Сравнению удовлетворяют классы и . Имеет ли это сравнение еще одно решение? Делим на , находим: так что и, следовательно, это сравнение имеет три решения. 3.5 Сравнения по простому модулю с несколькими неизвестнымиНекоторые из рассмотренных нами теорем можно легко обобщить на случай сравнений с несколькими неизвестными вида:
где многочлен с целыми коэффициентами, а простое число. Теорема 1. Если в левой части сравнения (3.24) некоторые из неизвестных встречаются в виде степени с показателем , то сравнение (3.24) можно заменить эквивалентным сравнением, в котором степень каждого из неизвестных не превосходит . Доказательство. Сравнение (3.24) эквивалентно сравнению где произвольный многочлен с целыми коэффициентами. Если среди слагаемых есть член вида где , то мы можем, взяв , заменить его членом , затем и т.д. Если где , то в показателе для можно отбросить и получить эквивалентное сравнение, в котором слагаемое будет заменено на Проделав такие операции для всех слагаемых по отношению к каждому из неизвестных, входящему с показателем , получим сравнение, эквивалентное первоначальному, в котором степень по отношению к каждому неизвестному будет не больше чем . Теорема 2. Если сравнение степень которого по каждому неизвестному меньше чем , удовлетворяется при всех целых , то все коэффициенты многочлена делятся на . Доказательство. Проведем индукцию по числу неизвестных . При утверждение теоремы верно. Предположим, что утверждение теоремы верно при , и возьмем произвольное тождественное сравнение , степень которого по каждому неизвестному меньше чем . Если наибольший показатель степени неизвестного , то сравнение можно представить в виде: где все многочлены с целыми коэффициентами, степени которых по каждому неизвестному меньше чем . Если вместо подставить любые целые числа, то получим тождественное сравнение с неизвестной степени . Все коэффициенты этого сравнения: должны при любых значениях делиться на . Поскольку согласно предположению для многочленов от аргументов утверждение теоремы верно, все коэффициенты этих многочленов, а следовательно, и многочлена должны делиться на . Согласно принципу полной математической индукции утверждение теоремы верно для любого числа аргументов. 4. Системы сравнений4.1 Системы сравнений первой степениСистему сравнений первой степени с одним и тем же неизвестным, но с разными модулями, запишем в общем виде так:
Общий способ (способ последовательного решения) состоит в том, что сначала находится из первого сравнения, где – наименьший неотрицательный или абсолютно наименьший вычет по модулю и берется класс чисел
удовлетворяющих первому сравнению. Затем это значение подставляется во второе сравнение, что дает откуда находится опять в виде класса чисел и подставляется в равенство ( . В результате получается значение в виде класса чисел, удовлетворяющих первым двум сравнениям системы. Дальше это значение подставляется в третье сравнение системы, так же находится , затем находится и подставляется в четвертое сравнение системы и т.д. Заметим, что можно идти и несколько иным путем: сначала решается каждое из сравнений системы и представляется в виде:
а затем поступают описанным способом. Если окажется, что хотя бы одно из сравнений системы (4.1) не имеет решения или сравнение относительно в описанном способе неразрешимо, то система (4.1) не имеет решения. Если для сравнений системы (4.1) и то, сокращая члены и модуль каждого сравнения на получаем систему:
эквивалентную (4.1). Сравнения этой системы можно решить относительно и свести решение системы (4.3) к решению системы:
Если в системе (4.2) модули попарно просты, то решение ее можно находить не указанным выше общим способом, а по формуле: где и есть решения сравнений: Решением системы будет: Этим способом можно решать и систему (4.4), если модули попарно просты. Пример 1. Решить систему сравнений: Классы вычетов по : при имеем: , следовательно, удовлетворяет первому сравнению системы, , следовательно, удовлетворяет второму сравнению системы. Поэтому класс вычетов является решением системы. Можно записать этот класс иначе: прибавив к модуль 9, получим, что Итак, данная система сравнений имеет решение ЗаключениеВ работе изложены основы теории сравнений. Задача данной курсовой работы разработка учебного пособия, которое содержит достаточный теоретический и практический материал. В данной работе достаточно полно изложены основные моменты теории, они иллюстрируются примерами, которые позволяют глубже понять рассматриваемые вопросы. Материал курсовой работы может быть использован как при изучении соответствующего курса теории чисел, так и для спецкурсов по алгебре, в частности, для тех специальностей, на которых нет курса теории чисел, уже на младших курсах обучения. Приведенный список литературы позволяет при необходимости рассмотреть некоторые более сложные моменты теории сравнений и их приложений. ЛитератураБухштаб А.А. Теория чисел. – М.: Просвещение, 1960. – 376 с. Алгебра и теория чисел: Уч. пособие. под ред. Н.Я. Виленкина. – М.: Просвещение, 1984. – 192 с. (гл. 3). Вахитова Е.В. Теория сравнений и ее приложения. – Стерлитамак: Изд-во СГПИ, 2000. – 414 с. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. – М.: Наука, 1984. – 288 с. Лельчук М.П., Полевченко И.И., Радьков А.М., Чеботаревский Б.Д. Практические занятия по алгебре и теории чисел. – Минск: Высш. Школа, 1986. – 302 с. (Занятия 46–51). Шнеперман Л.Б. Сборник задач по алгебре и теории чисел. – Мн.: Высш. шк., – 1982. – 223 с. Михелович Ш.Х. Теория чисел. М.: Высшая Школа, 1967. – 335 с. Грибанов П.И., Титов П.И. Сборник упражнений по теории чисел. М. Просвещение 1964. Александров В.А., Горшенин С.М. Задачник-практикум по теории чисел. М.: Просвещение 1960. – 48 с. |