ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Задания для аудиторной работы

Классы вычетов

Теоретические сведения

При делении целых чисел на натуральное целое существует различных остатков: Соответственно этим остаткам множество Z разбивается на непересекающихся классов сравнимых друг с другом чисел, т. е. имеющих один и тот же остаток от деления на В соответствии с остатками от деления на эти классы будем обозначать через . Таким образом, класс для каждого целого Любой представитель класса однозначно определяет свой класс: для каждого натурального числа класс . Поскольку остаток – по-латински residu – переводится на русский язык как вычет, то множество всех классов сравнимых друг с другом по данному модулю чисел называют множеством классов вычетов по модулю и обозначают через В силу сказанного – множество из элементов.

Заметим, что для любых классов и для произвольных суммы и принадлежат одному классу из так как эти суммы сравнимы друг с другом по модулю согласно свойству 2 сравнений (см. теоретический материал к первому разделу). Аналогично, произведения и лежат в одном классе из Определим операции сложения и умножения на Полагаем суммой Å тот единственный класс из в который попадают все суммы и для а произведением – тот класс из в который попадают произведения для произвольных

Поскольку сложение и умножение в однозначно определяются умножением представителей классов, то свойства 1 – 5 операций сложения и умножения целых чисел (см. раздел 1) справедливы и в

1) – коммутативность;

2) – ассоциативность;

3) существует нейтральный элемент: ;

4) для всякого существует единственный класс , такой, что , очевидно, им является класс = ;

5) – дистрибутивность.

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

Определение 2.1. Элемент называется обратимым, если найдется такой класс , что . Тогда класс называют обратным к классу .

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

Лемма 2.1. Пусть такой класс, что Тогда:

1) для каждого произведение ;

2) если

3) отображение инъективно и, следовательно, биективно на множестве (на множестве ненулевых элементов из );

4) – обратимый класс в кольце

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

Лемма 2.2. Пусть такой, что . Тогда:

1) существует класс , что ;

2) существуют классы такие, что

3) для всех произведение то есть класс не обратим в кольце

Теорема 2.1. Класс из кольца обратим тогда и только тогда, когда Если простое число, то в кольце каждый ненулевой класс обратим. Обратный класс также обратим. Произведение обратимых классов есть обратимый класс.

Поскольку состоит из конечного множества элементов, то сложение и умножение можно задавать поэлементно в виде таблиц.

Пример 2.1. Напишем таблицы сложения и умножения в кольце

Å

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

Определение 2.2. Функция Эйлера – функция натурального аргумента , которая каждому натуральному числу ставит в соответствие
количество натуральных чисел, меньших и взаимно простых c .

Перечислим основные мультипликативные свойства функции Эйлера.

Свойство 1. для каждого простого числа

Свойство 2. для каждого простого числа и для произвольного натурального

Свойство 3. Если то .

Свойство 4. Если – каноническое разложение числа то

Пример 2.2. Вычислим Поскольку то согласно свойству 4 значение

Пример 2.3. Из теоремы 2.1 следует, что в кольце имеется в точности обратимых классов. Например, Значит, в кольце имеется именно 4 обратимых элемента. Непосредственная проверка показывает, что этими классами являются .

Теорема 2.2 (теорема Эйлера). Если для целого числа и натурального , то

Алгебраическим сравнением -й степени с одной неизвестной называется сравнение вида

где .

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

Пример 2.4. Решить сравнение .

Решение. Среди чисел 0, 1, 2, 3, 4, 5, 6 полной системы вычетов по модулю 7 удовлетворяют данному сравнению только два числа: . Поэтому указанное сравнение имеет два решения:

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

Задания для аудиторной работы

Задание 2.1.Вычислить для всех натуральных от 2 до 12.

Задание 2.2.Вычислить

Решение. . Согласно свойству 4 функции Эйлера

. Поэтому согласно свойству 2 функции Эйлера

не делится на все простые 2, 3, 5, 7, меньшие 10. Следовательно, 89 – число простое. Поэтому

Задание 2.3.В кольцах и составить таблицы сложения и умножения. Найти в этих кольцах пары взаимно обратных по умножению элементов. Указать количество таких пар и сравнить это количество с и соответственно.

Решение аналогично решению примера 2.1.

Задание 2.4.В кольце классов вычетов по модулю 15 к каждому обратимому элементу найти обратный элемент.

Решениеможно получить, составив таблицу умножения в кольце Рассмотрим ниже другой путь решения этой задачи.

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

На языке сравнений равенство для выглядит как , а из теоремы Эйлера следует, что Умножив сравнение на , получим согласно свойствам сравнений. Последовательно вычисляем:

, следовательно, ;

;

Задание 2.5.Найти обратные к классам в кольце: а)
б)

Решение. Этот наибольший общий делитель найдем по алгоритму Евклида: Отсюда легко получается соотношение Безу для Согласно замечанию к лемме 2.1 Проверка:

Поэтому в кольце не существует