Euler's Totient Summation Formula Derivation
📂Number TheoryEuler's Totient Summation Formula Derivation
If n’s divisors are denoted by d1,d2,⋯,dr, then
n=i=1∑rϕ(di)=ϕ(d1)+ϕ(d2)+⋯+ϕ(dr)
Explanation
The totient function might feel somewhat unnatural from its definition. However, seeing Euler’s totient theorem and such formulas, one can’t help but acknowledge it as a necessary function somewhere within the truths of mathematics.
For example, for 15, it has the divisor 1,3,5,15. Actually calculating, it follows that
ϕ(1)+ϕ(3)+ϕ(5)+ϕ(15)===ϕ(1)+ϕ(3)+ϕ(5)+ϕ(3)ϕ(5)1+2+4+2⋅415
Derivation
Define F(n):=ϕ(d1)+ϕ(d2)+⋯+ϕ(dr) and show that F(n)=n holds.
Case 1. n is a prime
For the prime p raised to the power n=pk, it holds that
F(n)===ϕ(1)+ϕ(p)+⋯ϕ(pk)1+(p−1)+⋯+(pk−pk−1)pk
Case 2. n is the product of powers of two primes p,q
If we denote this by n=pkpqkq, then
F(n)=ϕ(1)+ϕ(p)+⋯+ϕ(pkp)+ϕ(q)+⋯+ϕ(qkq)+ϕ(pq)+ϕ(p2q)+ϕ(pq2)+⋯+ϕ(pkpqkq)
Due to the multiplicative nature of the totient function,
F(n)===ϕ(1)+ϕ(p)+⋯ϕ(pkp)+ϕ(q)+⋯ϕ(qkq)+ϕ(p)ϕ(q)+ϕ(p2)ϕ(q)+ϕ(p)ϕ(q2)+⋯ϕ(pkp)ϕ(qkq)[ϕ(1)+ϕ(p)+⋯ϕ(pkp)][1+ϕ(q)+⋯ϕ(qkq)]F(pkp)F(qkq)
Case 3. n is any natural number
By the fundamental theorem of arithmetic, it can be expressed as n=p1k1p2k2⋯psks.
F(n)===F(p1k1)F(p2k2)⋯F(psks)p1k1p2k2⋯psksn
Therefore, in any case F(n)=n holds.
■