Как можно с помощью обращения Мёбиуса получить явное представления функции Эйлера через каноническое разложение числа $%n$% на простые сомножители? задан 4 Апр 23:58 MsMe |
Как можно с помощью обращения Мёбиуса получить явное представления функции Эйлера через каноническое разложение числа $%n$% на простые сомножители? задан 4 Апр 23:58 MsMe |
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
4 Апр 23:58
показан
60 раз
обновлен
5 Апр 16:38
Примените обращения Мёбиуса к $%\sum_{d|n}\varphi(d)=n.$%
@EdwardTurJ, Можете пояснить, откуда это равенство берется? Точнее, почему оно справедливо?
@MsMe: это всё стандартные вещи, включая представление функции Эйлера. Проще посмотреть в учебниках.
Равенство следует из того, что все числа от 1 до n разбиваются на классы. В один класс попадают числа x, для которых НОД(x,n) равен d. Это равносильно тому, что x/d и n/d взаимно просты, а таких чисел ф(n/d). Получается сумма ф(n/d) по всем d|n. При этом n/d пробегает все делители n.