Задача 60775

Тема:    [ Функция Эйлера ]

Сложность: 4 Классы: 9,10,11 Название задачи: Тождество Гаусса.

Условие

Докажите тождество Гаусса  φ(d ) = n. Определение функции φ(n) см. в задаче 60758.

Решение

Рассмотрим ряд чисел из задачи 60774. С одной стороны, он состоит из n дробей. С другой стороны, все числа разбиваются на группы дробей с равным знаменателем d, каждая из которых состоит из φ(d) чисел.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	4
Название	Теоремы Ферма и Эйлера
Тема	Малая теорема Ферма
задача
Номер	04.149