Prove that $\sum_{c \mid d} f(c) = d$ The following problem is the beginning of an easy proof using Möbius inversion to prove that if $p$ is a prime, then there are exactly $\phi(d)$ incongruent integers having order $d$ modulo $p$.
Let $p$ be a prime number. Given a positive divisor $d$ of $p-1$, let $f(d)$ be the number of integers between $1$ and $p-1$ inclusive having order $d$. Show that $$\sum_{c \mid d} f(c) = d.$$
My logic so far has been to say that since every integer between $1$ and $p-1$ inclusive has order dividing $p-1$, so $$\sum_{d \mid p-1} f(d) = p-1.$$ Now is there a simple way to extend the result to $d$ instead of $p-1$?
 A: $\forall n \geq 1$:
$$\sum_{d \mid n} \phi(d)=n$$
Proof:
We define  the arithmetic function $F$ with:
$$F(n)=\sum_{d \mid n} \phi(d)$$
Suppose that $n$ is a power of a prime: $n=p^a$ with a prime $p$ and $a \geq 1$
Then,the positive divisors of $p^a$ are: $1,p, \dots,p^a$ and so:
$$F(p^a)=\phi(1)+\phi(p)+ \dots + \phi(p^a)=1+(p-1)+ \dots + (p^a-p^{a-1})=p^a$$
because the last sum is telescoping.
Because of the fact that $\phi$ is multiplicative,it implies that $F$ is also multiplicative.
Therefore, $F(1)=1$ and, if $n>1$ and  $n$ has the prime factorization
$n=p_1^{a_1} \cdots p_k^{a_k}$,then:
$$F(n)=F(p_1^{a_1}) \cdots F(p_k^{a_k})=n$$
So,it stands $F(n)=n , \forall n \geq 1.$
A: Let $g$ be a primitive root of $p$ be $g$ (it exists, since $p$ is a prime).
For all $n\in[1,p-1]$ there uniquely exists $r\in[1,\phi(p)]=[1,p-1]$ such that $g^r\equiv n\pmod p$. So $\{1,2,\ldots,p-1\}$ is same as $\{g^1,g^2,\ldots,g^{p-1}\}$, on $\Bbb Z/p\Bbb Z$. (This is the basic property of the primitive root.)
Since the order of $g^r$ is $\phi(p)/(\phi(p),r)$, if the order of $g^r$ is $d$, $(\phi(p),r)=\phi(p)/d$, and the number of such $r$ is $\phi(d)$.
Thus what we want to prove is:
$$\sum_{c\mid d}\phi(c)=d,$$
and that is the thing which evinda proved.
A: Interpreting your question in the same way as Evinda, here is a really nice proof of the resulting statement ($\sum_{d|n} \phi(d) = n$) that I learned from Pieter Moree.
Consider the fractions $\frac{1}{n}, \frac{2}{n}, \ldots, \frac{n}{n}$.
Clearly there are $n$ of them. If we all simplify them to lowest form, then each divisor $d$ of $n$ will appear as a denominator a number of times. Moreover the number of times denominator $d$ appears is equal to the number of enumerators that come with it, which is exactly the set of numbers smaller than and coprime to $d$.
So for each $d|n$ we get $\phi(d)$ fractions with denominator $d$ and in total there are still $n$ fractions, QED.
