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

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

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