Problem
NT-B2-M10-P005 The Sum of \(\varphi(d)\)
#5
★★★☆☆ Level 3 of 5
Prove that for every \(n\ge 1\), \(\sum_{d\mid n}\varphi(d)=n\).
1001 Problems in Classical Number Theory (method inspiration) · Problem 448
Count the fractions \(\frac{k}{n}\) after reduction.
Consider the numbers \(1,2,\ldots,n\). After reducing \(\frac{k}{n}\), its denominator becomes a divisor \(d\) of \(n\). For a fixed denominator \(d\), the numerator can be any number from \(1\) to \(d\) coprime to \(d\), giving \(\varphi(d)\) fractions. All \(n\) values of \(k\) are counted exactly once, so \(\sum_{d\mid n}\varphi(d)=n\).
One of the key identities of the module.