Prove that the sum of all positive integers k where 1 <= k <= n and gcd(k,n) = 1 is (1/2)n*phi(n).

I don't even know where to begin with this. We've been going over primitive roots in class lately so it probably has something to do with them, but I have no idea where they come into the problem.