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

Функция Эйлера j(а) определяется для всех целых положительных а и представляет собою число чисел ряда

0, 1, ...., a - 1, (1)

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

Пример:

j(1) = 1, j(4) = 2,

j(2) = 1, j(5) = 4,

j(3) = 2, j(6) = 2.

Теорема 1: Пусть

(2)

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

, (3)

или также

. (4)

В частности, будем иметь

. (5)

Доказательство: Применим (п. 4, Теорема 2). При этом числа d и числа f определим так: пусть x пробегает числа ряда (1); каждому значению x приведем в соответствие число d = (x, а) и число f = 1.

Тогда S' обратится в число значений d = (x, а), равных 1, т. е. в j(а). A S_d обратится в число значений d = (x, а), кратных d. Но (x, а) может быть кратным d лишь при условии, что d - делитель числа а. При наличии же этого условия S_d обратится в число значений x, кратных d, т. е. в . Поэтому

,

откуда ввиду (п. 4, Теоремы 1) следует формула (3), а из последней ввиду (2) следует формула (4).

Пример:

,

φ(81) = 81 – 27 = 54,

φ(5) = 5 – 1 = 4.

j(а) - мультипликативная функция, для которой при a > 0 имеем j(p^a) = p^a - p^a-1.

Это следует из формулы (4) и теоремы 2, п. 2.

Теорема 2: Имеем

.

В справедливости этой формулы убедимся, применяя тождество (п. 2, Теорема 4), которое при q(а) = j(а) дает

.

Ввиду (5) правая часть окажется равной

,

что после приведения в каждой большой скобке подобных членов обратится в

.

Пример: Полагая а = 12, находим

j(1) + j(2) + j(3) + j(4) + j(6) + j(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12.

Глава 3