= Totient divisor-sum identity
{title2=$\sum_{d\mid n}\varphi(d)=n$}
The <divisor sum> of <Euler's totient function> is the <identity arithmetic function>:
$$
\sum_{d\mid n}\varphi(d)=n,\qquad n>0.
$$
Equivalently, $\varphi*\mathbf1=\operatorname{id}$ under <Dirichlet convolution>, with $\mathbf1$ the <constant-one arithmetic function>. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781 lecture notes, Propositions 2.4.4 and 2.4.5]{ref}
To see why, group the <integers> $j=1,\ldots,n$ by $h=\gcd(j,n)$. Each $h$ is a positive <integer divisor> of $n$. Within its group, $j=ha$ with $1\leq a\leq n/h$ and $\gcd(a,n/h)=1$, by the <scaling identity for greatest common divisors>. Dividing by $h$ gives a <bijection> with the <integers> counted by $\varphi(n/h)$. The groups form a <partition of a set>, so
$$
n=\sum_{h\mid n}\varphi(n/h)=\sum_{d\mid n}\varphi(d).
$$
For $n=12$, the groups with <greatest common divisor> $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. <Möbius inversion> reverses this <divisor sum> to recover <Euler's totient function> from $g(n)=n$.
Back to article page
