# Another elementary enumeration

Let $\varphi(n);n\in \mathbb{N}$ denote the number of integers $1\le k\le n$ such that $(k,n)=1$ (Euler’s Phi Function). I read a proof of the following fact about the function proved using group theory; indicating the power ofgroup theory in enumerative combinatorics.

$\displaystyle\sum_{d|n}\varphi(d)=n$

Direct Proof: We shall assume that the reader is aware of the fact that $\varphi$ is multiplicative that is $\varphi(p_1^{\alpha_1} \dots p_k^{\alpha_k})=\varphi(p_1^{\alpha_1})\dots \varphi(p_k^{\alpha_k})$. We know that $\varphi(p^k)=p^k-p^{k-1}$. Let $m=p^k$, then

$\displaystyle\sum_{d|m}\varphi(d)=1+\sum_{t=1}^{k}p^t-p^{t-1}=p^k$

Considering the general case where $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$,

$\displaystyle \sum_{d|n}\varphi(d)=\sum_{d|n}\varphi\left( p_1^{\beta_1}\dots p_k^{\beta_n} \right)$ for every $\beta_i\le \alpha_i;1\le i \le k$.

$\displaystyle \sum_{d|n}\varphi(n)=\sum_{\beta_1=0}^{\alpha_1} \dots\sum_{\beta_n=0}^{\alpha_n}\varphi(p_1^{\beta_1}) \dots \varphi(p_n^{\beta_n})$

$\displaystyle\sum_{d|n}\varphi(n)=\prod_{i=1}^{k}\sum_{\beta_i=0}^{\alpha_i}\varphi(p_i^{\beta_i})=n$

Here is a simpler looking group theoretic proof.

There are exactly $\varphi(d)$ generators of the subgroup $\mathbb{Z}_d$ where $d$ is a divisor of $n$. Every element of $\mathbb{Z}_n$ is a generator of exactly one subgroup of $\mathbb{Z}_d$.