Results 1 to 2 of 2

Math Help - Reduced system of representatives

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    21

    Reduced system of representatives

    Show that if c1 , . . . , cφ(m) is a reduced system of representatives modulo any m > 2 then c + + c ≡ 0 (mod m).

    <<Completely lost.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by AgentNXP View Post
    Show that if c1 , . . . , cφ(m) is a reduced system of representatives modulo any m > 2 then c + + c ≡ 0 (mod m).

    <<Completely lost.
    c_1,c_2,...,c_{\phi(m)} leave different remainders which must be all relatively prime to n. Thus, by pigeonhole all must be distinct for otherwise two of them will leave the same remainder mod m. Thus, (c_1+c_2+...+c_{\phi(m)})\bmod m can be rearranged so that it is the sum of the first \phi(m) integers relatively prime to m. Say a_1,...,a_{\phi(m)} are the first m integers relatively prime to m, then m-a_1,...,m-a_{\phi(m)} are still relatively prime to m. Thus, (a_1+...+a_m) = (m+...+m) - (a_1+...+a_m), this means the sum of the first \phi(m) relatively prime integers is (1/2)m\phi(m). Since \phi(m) is even we can write (1/2)m\phi(m) = m [\phi(m)/2) which leaves remainder 0 upon division by m.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: August 31st 2011, 09:51 AM
  2. System of Distinct Representatives
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2010, 11:58 AM
  3. Primitive roots & Reduced residue system
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 4th 2010, 05:51 AM
  4. Reduced residue system modulo m
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 20th 2010, 08:12 PM
  5. Help with reduced row echelon form/solving system
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: March 23rd 2009, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum