# Show $\sum\limits_{d|n}\phi(d) = n$. [duplicate]

Show $\sum\limits_{d|n}\phi(d) = n$.

Example : $\sum\limits_{d|4}\phi(d) = \phi(1) + \phi(2) + \phi(4) = 1 + 1 + 2 = 4$

I was told this has a simple proof. Problem is, I can not think of a way to show this in a very simple and straightforward way.

-

## marked as duplicate by lhf, Rick Decker, Dan Rust, Danny Cheuk, Rebecca J. StonesSep 25 '13 at 0:50

Show it for prime powers (elementary), and then show that the sum is a multiplicative function, that means for $m,n$ coprime, you have $$\sum_{d\mid mn} \phi(d) = \left(\sum_{e \mid m} \phi(e)\right)\left(\sum_{g\mid n}\phi(g)\right).$$ – Daniel Fischer Sep 24 '13 at 22:28
Alternatively consider the set of cyclic subgroups of the multiplicative group and their corresponding orders. – Alex R. Sep 24 '13 at 22:32
Since this came from an abstract algebra course your idea Alex is probably the right direction to head in. Would you be able to provide an example of what your talking about Alex? – Steve Thomas Sep 24 '13 at 22:43

Hint: You can show that $\sum\limits_{d|n}\phi(d) = \sum\limits_{d|n}\phi(\frac{n}{d})$ but $\phi(\frac{n}{d})$ is all numbers with GCD of $d$ with $n$. Therefore the last sum counts all numbers till $n$ and is equal to $n$.

-
Nice reindexing argument. (+1) – robjohn Sep 24 '13 at 22:49
@robjohn, Thanks a lot! – Arash Sep 25 '13 at 13:36

Let $G=\langle x\rangle$ be the cyclic group of order $n$ generated by $x$. Then, \begin{align} n &= |G| \\ &= \sum_{1\leq d\leq n} |\{\text{elements of order } d\}| \\ &= \sum_{d|n}|\{\text{elements of order } d\}| \end{align} by Lagrange's Theorem. But $G$ has a unique cyclic subgroup of order $d$ for each $d|n$, namely $\langle x^{n/d}\rangle$. Moreover, each such subgroup has $\varphi(d)$ generators, so $$n = \sum_{d|n}\varphi(d)$$

-

Here's one approach:

Consider the polynomial $x^n-1$ as a polynomial over the complex numbers $\mathbb{C}$. You can easily see, almost tautologically, that

$$x^n-1=\prod_{d\mid n}\Phi_d(x)\qquad(\ast)$$

where $\Phi_d(x)$ is the polynomial whose roots are the primitive $d^{\text{th}}$ roots of unity (i.e. solutions to $x^d-1$ that do not satisfy $x^c-1$ for $0<c<d$).

But, rephrasing the definition, $\Phi_d(x)$ is the polynomial with roots $e^{\frac{2\pi i r}{d}}$ where $e^{\frac{2\pi r s}{d}}\ne 1$ for $0<s<d$. But, this is saying that $sr\not\equiv 0\mod d$ for $0<s<d$, or that $d$ and $r$ have no common factors. Since we only need to care about $r$ which are less than or equal to $d$ we see that, in fact, the are $\phi(d)$ such roots of $\Phi_d(x)$.

This allows us to conclude that $\deg \Phi_d(x)=\phi(d)$. Indeed, since $\Phi_d(x)\mid x^n-1$, and $x^n-1$ has no repeated roots in $\mathbb{C}$ (it's coprime to its derivative) we see that $\Phi_d(x)$ has no repeated roots. Thus, $\deg\Phi_d(x)$ is the number of roots of $\Phi_d(x)$ which is $\phi(d)$.

So, by comparing degrees in $(\ast)$ we get:

$$n=\sum_{d\mid n}\deg\Phi_d(x)=\sum_{d\mid n}\phi(d)$$

-
Cool proof. +1'ed. – Pedro Tamaroff Sep 24 '13 at 23:27

The simplest proof I know is this:

Consider all proper fractions of the form $a/n$. There are $n$ of those. When you consider their reduced forms you get fractions of the form $b/d$ with $d|n$ and $(b,d)=1$. By definition, there are $\phi(d)$ of those. The result follows.

-

Consider the set $[n]=\{1,1,2,\ldots,n\}$ of size $n$. Define an equivalence relation as follows $$m\sim m'\iff (m,n)=(m',n)$$ That this is an equivalence relation should be clear. The equivalence classes are of the form $$\widehat m=\{0<m'\leqslant n:(m',n)=d\}$$ where $d=(m,n)\mid n$. Now, what is the size of this class? It contains all positive elements $m'\leqslant n$ such that $(m',n)=d$, or what is the same, all positive elements $$\frac{m'}d\leqslant \frac nd$$ such that $$\left(\frac{m'}{d},\frac nd \right)=1$$

This amounts to $\varphi\left(\dfrac nd\right)$ elements. But there is one class for each positive divisor of $n$, thus we have paititioned our set getting $$n=\sum_{d\mid n}\varphi\left(\dfrac nd\right)$$

But as $d$ runs through all divisors of $n$; so does $\dfrac nd$, so that $$n=\sum_{d\mid n}\varphi(d)$$

-