Функция Эйлера и теорема Эйлера из ТЧ

Будем обозначать эту функцию за Посчитаем сначала её для степени простого числа У нас есть ровно остатка таких, что и не делятся на так что Теперь покажем, что мультипликативна. Пусть покажем, что Представим в виде прямоугольной таблицы столбцов), отметим столбцы, для номеров которых взаимно просты с Расположим числа слева-направо и сверху-вниз: в строке столбце стоит число Тогда взаимно просты с будут клетки, которые стоят в отмеченных столбцах. Теперь рассмотрим, какие остатки по модулю встречаются в рамках одного столбца. Там стоят числа вида Из взаимной простоты и получаем, что все эти остатки различны. Значит, в одном столбцу нам подойдёт ровно чисел. Таким образом, всего подходящих чисел как раз (поскольку столбцов Теперь остаётся сказать, что для простых верна формула из условия, значит, и для составных тоже.