Congruence of the sum of terms in a reduced residue system

[reyomit]

Homework Statement

Prove that if {r₁,r₂,...r_x} is a reduced residue system mod m (where x=\phi(m), m>2), then
r₁ + r₂ + ... + r_x= 0 mod m.

Homework Equations

The Attempt at a Solution

I've been able to prove it pretty simply for odd m and for m=2k where k is odd, but for m with higher powers of 2 as a divisor I'm stuck.
Any ideas?

 

[Tinyboss]

If gcd(a,m)=1, what can you say about gcd(m-a,m)?

 

[reyomit]

I see that (a,m)=1 immediately implies that (m-a,m)=1,and used that to prove that
2(r₁ + r₂ + ... +r_x) = 0 mod m.

Then when m is odd 2 has a multiplicative inverse mod m, and we can just multiply by that to get r₁ + r₂ + ... +r_x = 0 mod m.

But when m is even, I'm not totally sure, what to do.

 

[reyomit]

Let me be more explicit, using that (m-a,a)=1 whenever (m,a)=1, I concluded
(m-r₁)+(m-r₂)+...+(m-r_x)=r₁+...+r_x mod m
and also
(m-r₁)+(m-r₂)+...+(m-r_x)= -r₁-r₂-...-r_x mod m.

So -(r₁+...+r_x)=r₁+...+r_x mod m
or 2(r₁+...+r_x)=0 mod m.

 

[Tinyboss]

You're making it a little more complex than it is. First, notice that phi(m) is even for m>2. Then if gcd(a,m)=1, then gcd(m-a,m)=1 (as you found), so that both a and m-a are in the reduced residue system.

So, you can split the elements of the reduced residue system into pairs, each of which sums to m.

 

[reyomit]

I feel much the fool.
Thank you.