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

Число положительных целых чисел, не превосходящих и взаимно простых с , обозначается через числовая функция определенная на множестве всех целых положительных чисел, называется функцией Эйлера. Легко видеть, что равна числу неотрицательных целых чисел, меньших и взаимно простых с .

Пример:

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

ТЕОРЕМА 3.9. Функция Эйлера мультипликативна.

Доказательство. Пусть а и b — взаимно простые положительные целые числа. Рассмотрим множество М всех неотрицательных целых чисел, меньших Согласно теореме о делении с остатком, каждое число из М может быть единственным образом представлено в виде где Число взаимно простое с а тогда и только тогда, когда Существует таких . Пусть — одно из этих чисел. Тогда согласно предложению 2.2 числа образуют полную систему вычетов по модулю а. Поэтому среди этих чисел имеется точно чисел, взаимно простых с а. Таким образом, каждому числу взаимно простому с b, соответствует точно чисел вида взаимно простых с а, и, значит, с . Поэтому число чисел из М, взаимно простых с равно .

ТЕОРЕМА 3.10. Если — каноническое разложение натурального числа , то

Доказательство. Так как функция мультипликативна, то для вычисления достаточно уметь вычислять эту функцию для степени простого числа . Число целых неотрицательных чисел, меньших и не взаимно простых с равно так как только числа не взаимно простые с . Поэтому число чисел, меньших и взаимно простых с равно т. е.

Так как и функция мультипликативна, то

Из (2) и (3) следует, что

значит, верна формула (1).

Пример:

ТЕОРЕМА 3.11. Сумма чисел по всем натуральным делителям d числа равна , т. е.

Доказательство. Если — каноническое разложение , то

так как при раскрытии скобок получим сумму всех значений

Далее,