Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by lhf, Rick Decker, Daniel Rust, Danny Cheuk, Rebecca J. Stones Sep 25 '13 at 0:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
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
2  
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
add comment

5 Answers 5

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$.

share|improve this answer
    
Nice reindexing argument. (+1) –  robjohn Sep 24 '13 at 22:49
    
@robjohn, Thanks a lot! –  Arash Sep 25 '13 at 13:36
add comment

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)$$

share|improve this answer
add comment

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)$$

share|improve this answer
    
Cool proof. +1'ed. –  Pedro Tamaroff Sep 24 '13 at 23:27
add comment

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.

share|improve this answer
add comment

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)$$

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.