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

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

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

Очевидно, что число равно количеству чисел, которые образуют ПрСВ по модулю .

Примеры. ,. , , , ,, , , .

Свойства функции Эйлера.

1°. Если - простое число, то .

Действительно, среди чисел взаимно простых с будет .

2°. Если - простое число, то .

Действительно, среди чисел

в каждой группе (а групп ) взаимно простых с содержится ()- число, а всего и будет .

Определение 2. Числовая функция называется мультиплика-

тивной, если для каждого натурального функция и для всех взаимно простых натуральных чисел и (то есть )

.

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

Примеры. - мультипликативные функции.

3°. Функция Эйлера является мультипликативной функцией, то есть если , то

.

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

1, 2, 3, … , … ;

, , , … , … ;

, , , … , … ;

………………………………………………………………………….

, , , … , … ;

…………………………………………………………………………

, , , … , … .

Взаимно простыми с произведением будут, очевидно, те и только те числа, которые взаимно простые и с , и с . В каждой строке таблицы чисел, взаимно простых с , в каждом столбце таблицы чисел, взаимно простых с .

4°. Если каноническое разложение числа имеет вид , то

.

5°. (Тождество Гаусса) Сумма значений функций Эйлера для всех делителей числа равна : .

Пример 1. Сколько натуральных чисел взаимно простых с 528 и не превосходящих это число?

Решение. Используя мультипликативность функции Эйлера и формулу , где - простое число, вычислим функцию Эйлера:

.

Пример 2. Вычислить а) ; б) .

Решение. а) Так как , то по формуле

.

б) Так как , то или .

Упражнения.

№1. а) Дайте определение функции Эйлера.

б) Какими основными свойствами обладает функция Эйлера.

в) Напишите выражение для по каноническому разложению числа .

№2. Выпишите все классы вычетов по модулю 20 и найдите число

классов вычетов, взаимно простых с 20. Сравните ответ с данными, полученными по формуле Эйлера.

№3. Представить графически изменения функции Эйлера, где ─ нату-

ральное число.

№4. Напишите тождество Гаусса. Чему равна сумма:

а) ;

б) ?

№5. Вычислите:

а) ; б) ;

в) ; г) .

№6. Сколько существует положительных правильных несократимых дробей

вида при заданном числе ?

№7. Найдите число всех положительных правильных несократимых дробей

вида со знаменателем .

№8. Доказать, что при значение - число четное.

№9. Докажите, что если , то число натуральных чисел, не превосходя -

щих и имеющих с наибольшим общим делителем число , равно . Найдите это число, если а) , ; б) , ;

в) , ; г) , .

№10. Докажите:

а) .

б) ;

в) , , , где - натуральное;

г) Найдите критерий для каждого из этих случаев.

д)

№11. а) , где ;

б) , где и .

№12. Покажите, что сумма чисел, взаимно простых с числом и

меньших , вычисляется по формуле: .

№13. Решите уравнения:

а) ; ; ;

б) ; ;

в) ; ;

г) ; ; ; ;

д) ; ; .

№14. Доказать, что , имеет место сравнение ,

где - обобщенная функция Эйлера, определенная для всех нату-

ральных значений следующим образом:

, а при

НОК,

где - каноническое разложение числа .

№15. Доказать, что при всех , взаимно простых с , где

.

№16. Доказать, что существует составные модули , такие, что при всех

взаимно простых с имеет место сравнение . Найти

несколько таких значений .

№17. Доказать, что существует бесконечное множество составных

чисел таких, что (Дюпарк, 1955 г.)

№18. (Лиувилль) Пусть - четное число. Тогда .

№19. (Лиувилль) Пусть пробегает все нечетные делители числа , а - все четные делители числа . Тогда имеем .

№20. (Дирихле) Имеет место формула .

№21. Докажите, что в последовательности Фарея количество чисел равно .