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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:56, 11 мая 2016.

Определение

TemplateDifinitionIcon.svg Определение «Определение - Сравнимость двух целых чисел»
Два числа

Отношение эквивалентности

TemplateDifinitionIcon.svg Определение «Определение - Бинарное отношение»
Бинарное отношение - подмножество декартова произведения .

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

Отношение эквивалентности () на множестве  — это бинарное отношение, для которого выполнены следующие условия:

  1. Рефлексивность: для любого в ,
  2. Симметричность: если , то ,
  3. Транзитивность: если и , то .

Запись вида «» читается как « эквивалентно ».

Отношение эквивалентности делит все множества на классы эквивалентности.

Классом эквивалентности элемента называется подмножество элементов, эквивалентных . Из вышеприведённого определения немедленно следует, что, если , то . Множество всех классов эквивалентности обозначается .

Для класса эквивалентности элемента используются следующие обозначения: , , .

Множество классов эквивалентности по отношению является разбиением множества.

, то есть, классы эквивалентности либо совпадают, либо не пересекаются.

Следовательно,

- (фактор-множество)
TemplateTheoremIcon.svg Теорема Утверждение
Сравнимость () - отношение эквивалентности.
Доказательство
- классы вычетов по


Свойства

1.

2.

TemplateLemmaIcon.svg Лемма «Утверждение»


3.

TemplateLemmaIcon.svg Лемма «Утверждение»


Введем операцию умножения и сложения на классах:

Классы вычетов по mod m

TemplateTheoremIcon.svg Теорема Утверждение
  1. делитель нуля ;
  2. обратим .

Т.е. обратимы в точности все классы, взаимно простые с модулем.

Все обратимые элементы образуют группу по умножению, то есть, мультипликативную группу кольца вычетов:

Доказательство

Пусть

Рассмотрим

т.к. [1]

Таким образом,

- делители нуля.

Пусть

По расширенному алгоритму Евклида:

- обратный элемент для .

Обратимые элементы также образуют группу по умножению (мультипликативную группу кольца), т.к. очевидно, что .

- функция Эйлера.


Функция Эйлера

TemplateDifinitionIcon.svg Определение « Определение - Функция Эйлера»
Функция Эйлера , где  — натуральное число, равна количеству натуральных чисел, не больших и взаимно простых с ним.

Свойства

- простые.

Теорема Эйлера

TemplateTheoremIcon.svg Теорема Теорема Эйлера

Если и взаимно просты, то , где — функция Эйлера.

Доказательство

Пусть  — все различные натуральные числа, меньшие и взаимно простые с ним.

Рассмотрим всевозможные произведения для всех от до .

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

Перемножим все равенства .

Получим:

или

.

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

или

.


Частным случаем теоремы Эйлера (при простом ) является Малая теорема Ферма.

Малая теорема Ферма

TemplateTheoremIcon.svg Теорема Малая теорема Ферма

Если — простое число, и целое не делится на , то (или )

Доказательство

Очевидно следует из теоремы Эйлера при - простое, т.к. .


Функция Кармайкла

Подробнее можно прочитать здесь: Функция Кармайкла

Литература

Куликов Л. Я. Алгебра и теория чисел: Учеб. пособие для педагогических институтов. — М .: Высш. школа, 1979. — 559 с, ил.

Примечания

  1. LCM - least common multiple - НОК - наименьшее общее кратное