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

Решение.

Отсюда .

Определение. Функцией Эйлера называется функция , определенная на множестве N, значения которой равны числу k натуральных, может быть, и составных целых чисел, взаимно простых с n и не превосходящих n, т.е..

Для n=1 полагают . Знаком обозначается наибольший общий делитель натуральных чисел a и b. Взаимно простыми называются числа, наибольший делитель которых равен единице. Например, натуральные числа 5 и 7 взаимно просты, т.к. (5,7)=1.

Функция Эйлера аналитически выражается следующим образом:

, (1)

где к – есть число простых делителей q_i числа n, i=1;2;…;k.

Чаще функция Эйлера записывается в другом виде

. (2)

Посчитаем значения для n=1;2;…;10. Разложим в таблице1 числа с 1 до 10 на простые делители.

Таблица 1

1=1¹	6=2¹3¹
2=2¹	7=7¹
3=3¹	8=2³
4=2²	9=3²
5=5¹	10=2¹5¹

1. по определению.

2. , (1,2)=1. Это число1.

3. , (1,3)=1; (2,3)=1. Два числа не превосходят 3 и взаимно просты с числом 3; это числа 1 и 2.

4. , (1,4)=1; (3,4)=1. Это числа 1 и 3.

5. , (1,5)=1; (2,5)=1; (3,5)=1; (4,5)=1. Четыре числа удовлетворяют условию существования функции Эйлера. Это числа 1,2,3,4.

6. , (1,6)=1; (5,6)=1. то числа 1 и 5.

7. , (1,7)=1; (2,7)=1; (3,7)=1; (4,7)=1; (5,7)=1; (6,7)=1. Значения функции Эйлера в этом случае равно шести, т.к. шесть чисел удовлетворяют условию существования функции Эйлера. Это числа 1,2,3,4,5,6.