# Why is this fact about the totient function true? [duplicate]

This question already has an answer here:

$$\sum_{k<n} {gcd(k,n)=1}k = \frac{1}{2} n \phi(n)$$

This is a homework problem. I would ideally like to get to the final proof on my own. But at the moment I can't even decide how to begin.

The only relationship I can see between the sum and the right side of the equation is that the left adds all the things relatively prime with $n$ less than $n$, i.e., the things elements of the group $\Phi(n)$. The order of this group is $\phi(n)$. But that doesn't seem to help me in looking for a way about solving this.

## marked as duplicate by Thomas Andrews, Dennis Gulko, Ittay Weiss, muzzlator, Alexander Gruber♦Mar 22 '13 at 11:14

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.

## 1 Answer

Hint: Rearranging, we have $\frac{\sum k}{\phi(n)}=\frac{1}{2}n$. As you noticed, $\phi(n)$ is the number of summands. So we need only show that the average value of the elements of $\mathbb{Z}_n^\times$ is $\frac{n}{2}$.

Edit: by "average value of the elements of $\mathbb{Z}_n^\times$" I suppose I really mean to say "average value of the unique representatives $a<n$ for each class $[a]_n\in\mathbb{Z}_n^\times$"

• Correct, I believe the edit suffices. – user47805 Mar 22 '13 at 9:16