Задача
NT-B2-M10-P005 Сумма \(\varphi(d)\)
#5
★★★☆☆ Уровень 3 из 5
Докажите, что для каждого \(n\ge 1\) выполнено \(\sum_{d\mid n}\varphi(d)=n\).
1001 Problems in Classical Number Theory (method inspiration) · Задача 448
Посчитайте дроби \(\frac{k}{n}\) после сокращения.
Рассмотрим числа \(1,2,\ldots,n\). После сокращения дроби \(\frac{k}{n}\) её знаменатель становится некоторым делителем \(d\) числа \(n\). Для фиксированного знаменателя \(d\) числитель может быть любым числом от \(1\) до \(d\), взаимно простым с \(d\), то есть таких дробей \(\varphi(d)\). Все \(n\) значений \(k\) посчитаны ровно один раз, поэтому \(\sum_{d\mid n}\varphi(d)=n\).
Одна из ключевых идентичностей модуля.