Congruence of the sum of terms in a reduced residue system

1. Feb 25, 2010

reyomit

1. The problem statement, all variables and given/known data

Prove that if {r1,r2,...rx} is a reduced residue system mod m (where x=$$\phi$$(m), m>2), then
r1 + r2 + ... + rx= 0 mod m.

2. Relevant equations

3. 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?

Last edited: Feb 25, 2010
2. Feb 25, 2010

Tinyboss

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

3. Feb 25, 2010

reyomit

I see that (a,m)=1 immediately implies that (m-a,m)=1,and used that to prove that
2(r1 + r2 + ... +rx) = 0 mod m.

Then when m is odd 2 has a multiplicative inverse mod m, and we can just multiply by that to get r1 + r2 + ... +rx = 0 mod m.

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

4. Feb 25, 2010

reyomit

Let me be more explicit, using that (m-a,a)=1 whenever (m,a)=1, I concluded
(m-r1)+(m-r2)+...+(m-rx)=r1+...+rx mod m
and also
(m-r1)+(m-r2)+...+(m-rx)= -r1-r2-...-rx mod m.

So -(r1+...+rx)=r1+...+rx mod m
or 2(r1+...+rx)=0 mod m.

5. Feb 25, 2010

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.

6. Feb 25, 2010

reyomit

I feel much the fool.
Thank you.