Skip to main content

Discrete Mathematics · Recurrences, generating functions, and discrete asymptotics

Let n be a positive integer

Problem

Discrete Mathematics practice problem

Let nn be a positive integer. Prove that ∑d∣nφ(d)=n\sum_{d\mid n}\varphi(d)=n, where the sum runs over the positive divisors of nn.

Hint

Hint

Group the integers 1,…,n1,\dots,n according to their gcd with nn; the size of the block with gcd dd is a totient.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.

More Discrete Mathematics practice problems

Back to Discrete Mathematics

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.