Prove that $\sum_{c \mid d} f(c) = d$

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.