Методы теории сравнений

Введение

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

Основная часть курсовой работы состоит из трех глав. В первой главе раскрываются основные понятия теории сравнений, такие как сравнения в кольце целых чисел, основные теоремы и свойства сравнений. Во второй главе рассматриваются сравнения первой степени с одной переменной. Далее рассматриваются сравнения высших степеней и системы сравнений первой степени. В приложении приводятся примеры решения текстовых задач, которые сводятся к неопределенным уравнениям первого порядка и решаются с помощью сравнений.

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

В работе приводится список литературы по теме.

 

 

 

 

 

 

 

 

 

 

 

1. Теория сравнений

1.1 Сравнения в кольце  целых чисел

Понятие сравнения было введено впервые Гауссом. Несмотря на свою кажущуюся простоту, это понятие очень важно и имеет много приложений.

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

Определение. Целые числа  и называются сравнимыми по модулю , если разность делится на , т.е. если .

Таким образом, сравнение  представляет собой соотношение  между тремя числами  и , причем , играющее роль своего рода эталона сравнения, мы называем «модулем». Для краткости будем это соотношение между и записывать:

,

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

Если разность не делится на , то мы будем записывать:

.

Согласно определению, означает, что делится на .

1.2 Основные  теоремы о сравнениях

Теорема 1 (признак сравнимости двух чисел по модулю ). Два целых числа и сравнимы по модулю тогда и только тогда, когда и имеют одинаковые остатки при делении на .

Доказательство. Пусть  остатки при делении  и на равны, т.е.

	(1.1)
	(1.2)

где

Вычтем (1.2) из (1.1); получим  т.е. или

Обратно, пусть  это означает, что или

(1.3)

Разделим  на ; получим Подставив в (1.3), будем иметь т.е. при делении на получается тот же остаток, что и при делении на .

Пример 1. Определим, сравнимы ли числа  и по модулю .

Решение. При делении  и на получаются одинаковые остатки Следовательно,

Определение. Два или несколько  чисел, дающие при делении на одинаковые остатки, называются равно остаточными или сравнимыми по модулю .

Теорема 2. Отношение сравнимости  рефлексивно: .

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

Теорема 3. Отношение сравнимости  симметрично: если , то .

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

Теорема 4. Отношение сравнимости  транзитивно: если

то  .

Доказательство. Если остатки от деления  на одинаковы у чисел и , а также у и , то и тоже имеют одинаковые остатки при делении на .

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

Теорема 5. Если и произвольное целое число, то

.

Доказательство. Если , то , , , .

Теорема 6. Если и 1, то .

Доказательство. Если , то | , | , но тогда условие дает | , т.е. .

Теорема 7. Если и произвольное натуральное число, то .

Доказательство. Если , то | , | , .

Теорема 8. Если , где и произвольные натуральные числа, то .

Доказательство. Если , то | , | ,

натуральное ( , тогда | , .

Теорема 9. Если , , то и .

Доказательство. Если и , то и . Получим, что

Теорема 9'. Если , то .

Теорема 10. Если и , то .

Доказательство. Если и , то и . Тогда по транзитивности сравнений получим, что .

Теорема 10'. Если , то

.

Доказательство. Последовательно  применяя теорему 7, получим:

.

Теорема 11. Если , то при любом целом , .

Доказательство. При  утверждение верно по теореме 2, а при оно верно согласно теореме 10', если и .

Переход от сравнений  , к сравнениям

, ,

будем называть соответственно сложением (вычитанием), умножением, возведением  в степень сравнений.

Так как из сравнения  следует , то из сравнений и следует также, что и .

Теорема 12. Если и произвольный многочлен с целыми коэффициентами, то .

Доказательство. Если , то, согласно теоремам 7 и 11, имеем:

при .

По теореме 9', получаем ,

т.е. .

Теорема 12'. Если и многочлен с целыми коэффициентами, то

.

Теорема 13. Любое слагаемое левой  или правой части сравнения можно  перенести с противоположным  знаком в другую часть.

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

Следствие. В левой и правой частях сравнения можно добавлять или  отбрасывать одно и то же слагаемое.

Теорема 14. В сравнении можно  отбрасывать или добавлять слагаемые, делящиеся на модуль.

Доказательство. Если и , т.е. , то, складывая эти сравнения, получаем . Аналогично из и получаем .

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

Теорема 15. Если и , то .

Доказательство. Если , то . Из , в силу транзитивности отношения делимости получаем , .

Теорема 16. Если , то множество общих делителей и совпадает с множеством общих делителей и . В частности,

Доказательство. Если , то , , , любой общий делитель чисел и является общим делителем чисел и , и, наоборот, если и , то .

Поскольку пара и пара имеют одни и те же общие делители, то и .

Теорема 17. Если , , то , где .

Доказательство. Если , , то , то и, согласно свойствам наименьшего общего кратного, .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Сравнения  первой степени с одной переменной

2.1 Основные  понятия

Определение 1. Сравнением первой степени с одной переменной называется сравнение вида

(2.1)

где

Будем говорить, что целое  число  удовлетворяет сравнению (2.1), если верное сравнение.

Теорема 1. Если целое  число  удовлетворяет сравнению (*), то и весь класс по состоит из чисел, удовлетворяющих этому сравнению.

Доказательство. Имеем: , отсюда получим, что . Обозначим через разность , то есть . Следовательно, . А так как число удовлетворяет сравнению (2.1), то сравнение

(2.2)

является верным. Кроме  того,

Получим

(2.3)

Но тогда по свойству транзитивности из (2.2) и (2.3) получим, что 

,

то есть удовлетворяет сравнению (2.1), поэтому весь класс , состоит из чисел, удовлетворяющих сравнению (2.1). Теорема 1 доказана.

Определение 2. Решением сравнения (2.1) называется класс вычетов  по , которые при подстановке в сравнение обращают его в верное сравнение.

Число решений сравнения  по это число решений этого сравнения в какой-либо полной системе вычетов по модулю .

2.2 Теорема  о неразрешимости и разрешимости сравнения

Теорема 1. Пусть дано сравнение

(2.4)

, . Тогда сравнение (2.4) не имеет решения.

Доказательство. От противного. Предположим, что существует решение: класс вычетов по mod m. Тогда удовлетворяет сравнению, то есть верное сравнение. Отсюда получим, что

(2.5)

Из условия теоремы: следует, что

(2.6)

Поэтому из (2.5) и (2.6) получим, что  и , отсюда следует, что . Получили противоречие: так как сделали неправильное предположение. Отбросив его, получим, что сравнение (2.4) не имеет решения. Теорема 1 доказана.

Рассмотрим сравнение:

(2.7)

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

Пусть теперь , тогда будем иметь:

Поэтому получим: . Так как по определению НОД число , то из последнего сравнения получим:

Таким образом, полагая  в (1), что НОД , мы пришли к сравнению такого же вида, но с условием: . Исследуем этот случай.

Теорема 1. Пусть дано сравнение (2.7) и НОД . Тогда сравнение (2.7) имеет единственное решение.

Доказательство. Так как  НОД , то класс вычетов по mod m принадлежит мультипликативной группе классов вычетов, взаимно простых с mod m. Поэтому (по свойству группы) уравнение имеет единственное решение , где класс вычетов по mod m, взаимно простых с m. Значит, для , но тогда , отсюда . Обозначим через класс вычетов no mod m, тогда получим, что для следовательно, , a верное сравнение, то есть класс является решением сравнения (2.7). Это решение единственно, так как существует единственный класс . Теорема 1 доказана.

Заметим, что для нахождения решения сравнения первой степени  с одной переменной (если оно есть) существует несколько способов:

1) подбора; 

2) преобразования коэффициентов; 

3) Эйлера (с помощью  функции Эйлера);

4) цепных дробей.

Если модуль m является простым числом, то есть , число не делится на , то сравнение имеет единственное решение. Следовательно, множество классов вычетов образует поле по отношению сложения и умножения классов вычетов. Его обозначают через

 

 

 

 

 

 

 

 

3. Сравнения  высших степеней

3.1 Основные  понятия

Определение 1.Сравнением n-й степени с одной переменной называется сравнение вида

(3.1)

где многочлен с целыми коэффициентами:

(3.2)

причем, .

Целое число  удовлетворяет сравнению (3.1), если сравнение является верным сравнением.

Теорема 1. Пусть дано сравнение (3.1) и целое число  удовлетворяет сравнению (3.1). Тогда весь класс по mod m состоит из чисел, удовлетворяющих сравнению (3.1).

Доказательство. Число  удовлетворяет сравнению (3.1), следовательно, верное сравнение. Для любого всегда . Но тогда по свойству сравнений , поэтому по транзитивности получим, что , отсюда следует, что число удовлетворяет сравнению (3.1). А так как произвольное из , то, следовательно, весь класс вычетов по mod m состоит из чисел, удовлетворяющих сравнению (3.1). Теорема 1 доказана.

Определение 2. Решением сравнения (3.1) называется класс вычетов по модулю m, состоящий из чисел, удовлетворяющих сравнению (3.1).

Если класс  mod m является решением сравнения (3.1), то будем говорить, что класс удовлетворяет сравнению (3.1). Числом решений сравнения (3.1) называется число классов вычетов по mod m, удовлетворяющих сравнению (3.1).

Задача нахождения чисел, удовлетворяющих сравнению (3.1), сводится к нахождению классов, удовлетворяющих уравнению

Действительно:

· так как  верно, то

· обратно, если , то , следовательно,

Чтобы решить сравнение  , можно

1) взять любую полную  систему вычетов по mod m:

2) вычислить 

3) взять те числа  , при которых сравнение является верным, то есть Соответствующие классы , дадут все решения сравнения.

Удобнее брать полную систему наименьших по абсолютной величине вычетов по mod . Если сравнение имеет несколько решений , то эти решения можно записывать в виде (то есть принимает любые значения, сравнимые с одним из чисел ) вместо записи

Задача нахождения решения  сравнения  проще, чем рассматриваемая в курсе алгебры задача нахождения решения уравнения . Так как решая уравнение в некотором бесконечном множестве (R, С) нельзя перебрать все числа . А решая сравнение , ищем решение в конечном кольце Zm классов вычетов по mod m. Следовательно, с помощью конечного числа операций можно найти все решения. Но надо заметить, что при больших m будут громоздкие вычисления, поэтому надо изучить способы, позволяющие определить число решений, а иногда и способы нахождения решения с помощью возможно меньшего числа операций.

3.2 Сравнения  вида 

Рассмотрим сравнение с одной переменной вида

(3.3)

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

Определение 1.Решением сравнения (3.3) называется класс вычетов по mod m, состоящий из чисел, удовлетворяющих этому сравнению.