1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Congruence of the sum of terms in a reduced residue system

  1. Feb 25, 2010 #1
    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=[tex]\phi[/tex](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. jcsd
  3. Feb 25, 2010 #2
    If gcd(a,m)=1, what can you say about gcd(m-a,m)?
  4. Feb 25, 2010 #3
    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.
  5. Feb 25, 2010 #4
    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.
  6. Feb 25, 2010 #5
    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.
  7. Feb 25, 2010 #6
    I feel much the fool.
    Thank you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook