logo

Euler's Totient Summation Formula Derivation 📂Number Theory

Euler's Totient Summation Formula Derivation

Formulas

If nn’s divisors are denoted by d1,d2,,drd_{1}, d_{2} , \cdots , d_{r}, then n=i=1rϕ(di)=ϕ(d1)+ϕ(d2)++ϕ(dr) n = \sum_{ i = 1 }^{r} \phi (d_{i}) = \phi (d_{1}) + \phi (d_{2}) + \cdots + \phi (d_{r})

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 1515, it has the divisor 1,3,5,151,3,5,15. Actually calculating, it follows that ϕ(1)+ϕ(3)+ϕ(5)+ϕ(15)=ϕ(1)+ϕ(3)+ϕ(5)+ϕ(3)ϕ(5)=1+2+4+24=15 \begin{align*} \phi (1) + \phi (3) + \phi (5) + \phi (15) =& \phi (1) + \phi (3) + \phi (5) + \phi (3) \phi (5) \\ =& 1 + 2 + 4 + 2 \cdot 4 \\ =& 15 \end{align*}

Derivation

Define F(n):=ϕ(d1)+ϕ(d2)++ϕ(dr)F(n) := \phi (d_{1}) + \phi (d_{2}) + \cdots + \phi (d_{r}) and show that F(n)=nF(n) = n holds.


Case 1. nn is a prime

For the prime pp raised to the power n=pkn = p^{k}, it holds that F(n)=ϕ(1)+ϕ(p)+ϕ(pk)=1+(p1)++(pkpk1)=pk \begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots \phi (p^{k}) \\ =& 1 + (p-1) + \cdots + (p^{k} - p^{k-1}) \\ =& p^{k} \end{align*}


Case 2. nn is the product of powers of two primes p,qp,q

If we denote this by n=pkpqkqn = p^{k_{p}} q^{k_{q}}, then F(n)=ϕ(1)+ϕ(p)++ϕ(pkp)+ϕ(q)++ϕ(qkq)+ϕ(pq)+ϕ(p2q)+ϕ(pq2)++ϕ(pkpqkq) \begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots + \phi (p^{k_{p}}) + \phi (q) + \cdots + \phi (q^{k_{q}}) \\ & + \phi (pq) + \phi (p^{2}q) + \phi (pq^{2}) + \cdots + \phi (p^{k_{p}} q^{k_{q}}) \end{align*} 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) \begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots \phi (p^{k_{p}}) + \phi (q) + \cdots \phi (q^{k_{q}}) \\ & + \phi (p) \phi (q) + \phi (p^{2}) \phi (q) + \phi (p) \phi (q^{2}) + \cdots \phi (p^{k_{p}}) \phi ( q^{k_{q}}) \\ =& \left[ \phi (1) + \phi (p) + \cdots \phi (p^{k_{p}}) \right] \left[ 1 + \phi (q) + \cdots \phi (q^{k_{q}}) \right] \\ =& F(p^{k_{p}}) F(q^{k_{q}}) \end{align*}


Case 3. nn is any natural number

By the fundamental theorem of arithmetic, it can be expressed as n=p1k1p2k2psksn = p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{s}^{k_{s}}. F(n)=F(p1k1)F(p2k2)F(psks)=p1k1p2k2psks=n \begin{align*} F(n) =& F(p_{1}^{k_{1}}) F(p_{2}^{k_{2}}) \cdots F(p_{s}^{k_{s}}) \\ =& p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{s}^{k_{s}} \\ =& n \end{align*} Therefore, in any case F(n)=nF(n) = n holds.