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