Элементы теории чисел и общей алгебры

I. Введение

I. 1. Предмет алгебры и теории чисел

I.2. Основные понятия и обозначения из теории множеств математической логики

Литература к разделу:

1. Кострикин А. И. Введение в алгебру.− М.: Наука, 1977.

2. Виноградов И. М. Основы теории чисел.− М.: Наука, 1965.

II. Элементарная теория чисел

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

Замечание. Традиционно в теории чисел неэлементарными считаются доказательства, в которых используются мнимые числа. Геометрические, алгебраические, аналитические, вероятностные методы − предмет более продвинутого изучения.

Далее используются обозначения:

ℕ = {1, 2, 3, …} − множество натуральных чисел;

ℤ = {0, 1, 2, 3, …} − множество целых чисел.

II.1. Теория делимости в ℤ

Число называется делителем числа , если для некоторого . В свою очередь называется кратным числа . Факт делимости обозначается как (читается: делит , или делится на ), а отрицание делимости как (читается: не делит , или не делится на ). Отношение делимости транзитивно: если и , то . Отметим также: если , и , то .

Натуральное число называется простым, если все его натуральные делители исчерпываются числами и . Натуральное число , не являющееся простым, называется составным. Число играет особую роль, его обычно не относят ни к простым, ни к составным. Такое соглашение полезно при формулировке большинства теоретико-числовых результатов.

Теорема Евклида. Множество ℙ простых чисел бесконечно.

Доказательство ( от противного ). Допустим, что множество ℙ конечно и состоит из чисел , ,…, .Тогда число является составным и представимо в виде для некоторых и , и, следовательно,

.

Последнее равенство, однако, невозможно, так как делителями единицы в ℤ являются лишь 1 и −1. Значит, не может быть конечным множеством. ∎

Теорема (о делении в ℤ с остатком). Для любых и существуют единственные , , такие, что

, .

Числа и называют соответственно частным и остатком от деления на .

Доказательство. Рассмотрим множество чисел

, .

Так как , и , то ( не пусто). Пусть − наименьшее число в . По условию, . Если допустить, что , то , а это противоречит выбору числа . Значит, . Остаётся доказать, что числа и могут быть выбраны единственным способом. Допустим, что существуют , такие, что , . Тогда Для определённости, считаем, что . Тогда

и . ∎

Для чисел и введём операции div и mod, полагая , , где и − соответственно частное и остаток от деления на .

Пусть числа , не равны нулю одновременно. Наибольшее такое, что и , называется наибольшим общим делителем чисел и и обозначается символом , (или как нод , , если возникает коллизия обозначений с векторами).

Алгоритм Евклида вычисления нод , основан на использовании следующих свойств:

1) , ;

2) , , ;

3) , ,

и осуществляется по схеме:

a:=abs(a); b:=abs(b);

while (a >0)&(b >0) do {

if a>b then a:=a mod b else b:=b mod a};

нод:=a+b.

Этот алгоритм затрачивает O времени (по числу арифметических операций). Анализ этого и других алгоритмов вычисления нодсм. у Д. Кнута (т. 2, § 4.5.2, 4.5.3).

Если , , то числа и называются взаимно простыми.

Теорема. Пусть , , . Тогда существуют , такие, что

, ;

в частности, если и взаимно просты, то для некоторых , .

Доказательство. Положим

, }.

Выберем в наименьшее положительное число . Запишем число в виде , где . Имеем . Поскольку

, то (по условию выбора ), и, следовательно, . Аналогично получаем, что . Пусть − любой общий делитель чисел и . Тогда

, ,

откуда следует, что число обладает свойствами , . ∎

Наибольший общий делитель чисел , , …, может быть вычислен по схеме:

нод (, , …, ) = нод (, , ,…, )).

Лемма. Пусть , , − простое число. Тогда, если , то либо , либо (либо и то, и другое).

Доказательство. Допустим, что . Тогда , и для некоторых , . Умножая обе части последнего равенства на , получим . Так как , то . ∎

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

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

− два разложения числа на простые сомножители , . Тогда из предыдущей леммы следует, что делит одно из чисел , , …, . Пусть, для определённости . Поскольку − простое число, то = . Переходя к равенству , получаем аналогично, что = , и так далее. ∎

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

,

где − различные простые числа, , , …, . Такое преставление называется каноническим разложением числа на простые множители.

Пример. .

Замечание. Доказать данную теорему, опираясь только на мультипликативные свойства (т.е. свойства умножения и деления) целых чисел невозможно. Необходимо привлечение аддитивных свойств (т.е. свойств сложения). Это можно проиллюстрировать на примере множества , 4, 6,…} чётных чисел. Оно замкнуто относительно умножения: , . Всякое число представимо в виде произведения чисел ,…, , каждое из которых неразложимо в . Такие числа назовём - простыми. К ним относятся 2, 6, 10, 16,…,т.е. числа вида . Очевидно, что первая часть Основной теоремы выполняется. Однако вторая часть (об однозначности разложения) для неверна, поскольку некоторые числа из имеют более одного разложения в произведение -простых чисел. Например, 180 = 6∙30 = 18∙10, где ни одно из чисел 6, 30, 18, 10 не разлагается в произведение чётных чисел, т.е. эти числа являются -простыми. Такими же свойствами обладают множества , , ,… , , , ,… и др.(См. Радемахер и Теплиц, с. 249, прим. 39.)

Наименьшее общее кратное чисел , , , определяется как наименьшее число такое, что и , и обозначается символом , (или нок , ).

Теорема. Пусть , . Тогда

, , .

Доказательство. Пусть и − канонические разложения чисел и , , , , , , …, . Тогда

II.2. Сравнения в ℤ

Пусть . Числа , называются сравнимыми по модулю , если при делении на они дают одинаковые остатки. При этом пишут

.

Запись означает, что для чисел и сравнение не имеет места.

Отметим следующие свойства сравнений:

;

;

;

и

(свойства означают, что отношение сравнимости рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности на множестве ℤ);

и ,

где символ может быть заменён на любой из символов: (сложение), − (вычитание) или ∙ (умножение), но на один и тот же в обеих частях сравнения, так что сравнения можно почленно складывать, вычитать и перемножать);

≡ , ;

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

;

;

если , , , , нод , , то

,

т.е. обе части сравнения можно разделить на любой общий делитель при условии, что этот делитель взаимно прост с модулем;

(mod ),

т.е. обе части сравнения и модуль можно разделить на любой их общий делитель;

, где нок , ;

, , и ;

, , .

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

.

Нетрудно установить, что

,

.

Другими словами, классы , ,…, попарно не пересекаются, и любой класс совпадает с одним из них. Следовательно, имеет место следующее разбиение на непересекающиеся классы:

.

Каждое число из класса называется вычетом по модулю по отношению ко всем числам того же класса. Взяв по одному вычету из каждого класса, получим систему вычетов, которую называют полной системой вычетов по модулю . В частности, множество

, 1, …,

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

Теорема. Пусть , и − любые числа, нод (, ) = 1. Тогда, если пробегает полную систему вычетов по модулю , то также пробегает полную систему вычетов по модулю .

Доказательство. Если , то из свойств сравнений следует, что . Поэтому, если , то . ∎

Приведённая система вычетов по модулю . Функция Эйлера.

В разбиении на классы , ,…, удалим те классы , для которых нод , . Из оставшихся классов (для них нод , ) возьмём по одному вычету. В результате получим систему вычетов, которую называют приведённой системой вычетов по модулю . Как ив случае полной системой вычетов выбор приведённой системы вычетов не однозначен.

Теорема. Пусть нод (, . Тогда, если пробегает приведённую систему вычетов по модулю , то также пробегает приведённую систему вычетов по модулю .

Доказательство. Если , то . Поэтому, если (mod ), то . Остаётся учесть, что нод (, . ∎

Функция Эйлера определяется как количество чисел среди , , …, , взаимно простых с . Любая приведённая система вычетов по модулю содержит вычетов.

Первые значений :

Далее будет установлена формула для этой функции.