Материал: Ответы на экзаменационные вопросы по дискретной математике

Пример. Для числа существует меньших его и взаимно простых с ним чисел , поэтому .

Первые 99 значений функции Эйлера:

Таблица 6

Теорема. Если натуральное число имеет разложение на простые множители , то функция Эйлера равна:

Пример. Вычислим функцию Эйлера .

Мультипликативная функция — функция , в которой для любых взаимно-простых справедливо: .

Очевидно, что функция Эйлера — мультипликативная.

Теорема Эйлера. Для любого модуля и любого числа , взаимнопростого с числом , имеет место формула Эйлера: .

Пример. Найти остаток от деления числа на . Заметим, что числа 174 и 13 взаимно просты. Сначала вычислим значение функции Эйлера от делителя:

Затем разделим показатель степени 249 на с остатком: .

Тогда .

По теореме Эйлера , тогда , откуда , и таким образом , получаем и так как , то с учётом , получим . , то есть . Окончательно получаем: , то есть остаток при делении равен 5.

Теорема. Пусть — главный идеал кольца . Тогда множество классов вычетов по модулю образуют коммутативное кольцо с 1 с операциями сложения и умножения:

Действительно, все аксиомы кольца очевидны при таких введённых операциях сложения и умножения. Нулевой элемент — это (), единичный элемент — это (), для любого элемента можно образовать противоположный такой, что .

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

Таким образом, кольцо — кольцо классов вычетов по модулю (по идеалу ). Кольцо обозначается так: …

Пример. Кольцо.

Пример.

(или ) — кольцо классов вычетов по модулю 3.

.

.

.

Противоположный это . Действительно, .

11. Характеристика кольца. Теорема о характеристике кольца без делителей 0. Примеры. Кольцо классов вычетов. Примеры Характеристика кольца

Характеристика кольца с 1 — целое положительное число , для которого выполняется и никакое другое положительное число, меньшее , этим свойством не обладает. Если такого нет, то говорят, что кольцо имеет характеристику 0.

Примеры.

1. Кольцо имеет характеристику 0, так как ; кольцо также имеет характеристику 0.

2. Кольцо , то есть множество классов вычетов по , имеет характеристику . Действительно . В частности, кольцо , то есть множество классов вычетов по модулю 3: , так как , то есть характеристика равна 3.

Лемма. Если характеристика кольца равна , то для любого .

Теорема. Характеристика любого кольца без делителей 0 (в частности, поля) либо 0, либо простое число.

Действительно, если нет делителей 0, то есть нет таких чисел , что , то из определения характеристики следует, что либо , либо — простое, так как в противном случае и, следовательно, , то есть имеются делители 0. Теорема доказана.