Show that $$\sum_{m|n,\; m>0}\phi(m)=n$$ where $\phi$ is Euler's totient function.

What I did:

There are $n-\phi(n)$ elements in the set $S_1=\{m:m|n,\;0<m<n\}$. This set is nonempty if $n>1$ since $1$ is in the set. Since it is a finite set of integers, there exists a maximum, call it $n_1$. Then there are $n-\phi(n)-\phi(n_1)$ elements in the set $S_2=\{m:m|n,\;0<m<n_1\}$. Since we can continue this process until we get the empty set, then we arrive to the conclusion that $n-\sum_{m|n}\phi(m)=0$.

Is this proof correct?

The book I took it from suggests using the following facts: $\phi(m)$ counts the number of generators of the cyclic group $C_m$, that every element of $C_n$ generates a subgroup of $C_n$, and that every subgroup of $C_n$ is isomorphic to $C_m$ for some $m|n$.

  • $\begingroup$ a function $f$ on the natural numbers is called "multiplicative" if, whenever $\gcd(a,b) = 1,$ we also get $f(ab) = f(a) f(b).$ The Euler totient $\phi(n)$ is multiplicative. A multiplicative function is completely determined by the values it takes on primes and prime powers. Finally, if $f$ is multiplicative, so is $g(n) = \sum_{m|n} f(m)$ $\endgroup$
    – Will Jagy
    Jul 28 '17 at 23:25
  • 1
    $\begingroup$ For reference, this question defines the totient function for the first time and then asks this question subsequently, without trying to show its properties. $\endgroup$
    – George
    Jul 28 '17 at 23:28
  • 1
    $\begingroup$ @George I'm afraid your proof won't work. The reason is that not all numbers less than n that aren't relatively prime to n actually divide n. Take 18 and 16. They're not relatively prime. But 16 doesn't divide 18... $\endgroup$
    – user403337
    Jul 29 '17 at 0:43
  • $\begingroup$ The proof in silverman uses the fact that phi is multiplicative; and I believe this is essentially the Chinese remainder theorem. .. $\endgroup$
    – user403337
    Jul 29 '17 at 1:39

The intended solution seems to be this: we have $n$ elements in $C_n$. Now for each element $a$ of $C_n$, consider the subgroup $\langle a\rangle$, the cyclic subgroup generated by $a$. This is isomorphic to some $C_m$ for some $m\mid n$. Now group the elements by this $m$. Note that there are $\varphi(m)$ elements that generate $C_m$. Thus, summing across the $m$ gives the right hand side. On the other hand, we started with $n$ elements so this gives the left hand side.

This is the algebraic version of this combinatorial proof: write down the fractions $1/n, 2/n, \dots, n/n$ and simplify them. Then, $\varphi(m)$ of the fractions will have denominator $m$, but we have $n$ fractions, so we have the desired identity.


$\phi(n)$ is the number of integers relatively prime to n. So $\phi(n) - n$ is the number of integers that are not relatively prime to $n$, but not necessary divisors of $n$. But in your definition of $S_1$ you are only counting divisors of $n$.

For the proof using group theory take a look at this:

Difficulty understanding the proof that $n=\sum_{d|n} \phi(d) $


Following Silverman, first let $F (n)=\sum_{d|n}\phi (d)$ and prove $F (p^n)=p^n $(use $\phi (p^n)=p^n-p^{n-1}$ to get a "telescoping" sum). Then use the multiplicative property of $\phi $ to get (easily) that F is multiplicative. Then write $n={p_1}^{n_1}{p_2}^{n_2}\dots {p_k}^{n_k} $ and finish the proof...

Or you could use the method of Gauss, which is probably the slickest I've seen https://en.m.wikipedia.org/wiki/Euler%27s_totient_function. See "divisor sum"...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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