Divide with residue , so
As you said, if k is divisible by q then r = 0 and the sum is trivially = q, otherwise:
Take a q-th root of unity s.t. (why must there be such a root?), so:
the last equality fowllowing because... ,and then
, and we're done.
Pd. The above proof assumes you know a little group theory and that the q-th roots
of unity are a (cyclic) a group under complex multiplication.