.

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.

Tonio

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.