3. Приведенная система вычетов и примитивные классы.

Предложение 6. Пусть Тогда н. о. д.

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

В частности, если одно из чисел класса по модулю m взаимно просто с то и все числа этого класса взаимно просты с .

Классы, состоящие из чисел, взаимно простых с модулем, называются примитивными классами. Для любого модуля примитивные классы существуют; такими будут, в частности, классы 1 и предложение 7. Для того чтобы сравнение имело решение, необходимо и достаточно, чтобы а было взаимно просто с

Доказательство. Необходимость. Пусть существует целое число такое, что Число 1 взаимно просто с , значит (предложение 6), число взаимно просто с , откуда а взаимно просто с , что и требовалось доказать.

Достаточность. Пусть а взаимно просто с . Тогда, согласно предложению 5 § 1, существуют целые числа и и v такие, что Ясно, что , так что и есть решение сравнения

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

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

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

Число примитивных классов по модулю обозначается . Так определенная функция называется функцией Эйлера. Ясно, что . Для равно, очевидно, числу взаимно простых с чисел ряда . Так, и т. д.

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

Предложение 8. Сравнение , если а взаимно просто с , имеет единственный класс решений.

Доказательство. Пусть а — решение сравнения Ясно, что есть решение сравнения ибо . Если — какое-либо решение сравнения , то откуда ибо .

В терминах классов предложение 8 означает, что возможно деление на примитивный класс: уравнение имеет единственное решение

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

Имеет место следующая теорема, носящая имя Эйлера.

Теорема Эйлера. Если а и m взаимно просты, то

Доказательство. Пусть — числа, взятые по одному из каждого примитивного класса, так что . Пусть а взаимно просто с . Тогда числа тоже взаимно просты с , т. е. принадлежат примитивным классам. Все они попарно несравнимы между собой. Действительно, если , то в силу предложения , что возможно только если равны. Итак, числа лежат в разных классах и, так как их число равно числу классов, среди них имеется по одному из всех классов человек в 10 комнатах, ни в одной нет двоих, следовательно, все комнаты заняты»). Поэтому числа сравнимы с расположенными, быть может, в другом порядке. Запишем это:

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

Но так как сомножители различаются только порядком. Итак,

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

В терминах классов теорема Эйлера выглядит так: если а — примитивный класс по модулю

Важным частным случаем теоремы Эйлера является теорема Ферма: если — простое число и а не делится на то . Она непосредственно следует из теоремы Эйлера, ибо Теорему Ферма часто записывают в равносильной . В этой записи предположение о том, что а не делится на , становится излишним.

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