Results 1 to 2 of 2

Thread: 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
    10
    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.
    $\displaystyle c_1,c_2,...,c_{\phi(m)}$ leave different remainders which must be all relatively prime to $\displaystyle n$. Thus, by pigeonhole all must be distinct for otherwise two of them will leave the same remainder mod m. Thus, $\displaystyle (c_1+c_2+...+c_{\phi(m)})\bmod m$ can be rearranged so that it is the sum of the first $\displaystyle \phi(m)$ integers relatively prime to $\displaystyle m$. Say $\displaystyle a_1,...,a_{\phi(m)}$ are the first $\displaystyle m$ integers relatively prime to $\displaystyle m$, then $\displaystyle m-a_1,...,m-a_{\phi(m)}$ are still relatively prime to $\displaystyle m$. Thus, $\displaystyle (a_1+...+a_m) = (m+...+m) - (a_1+...+a_m)$, this means the sum of the first $\displaystyle \phi(m)$ relatively prime integers is $\displaystyle (1/2)m\phi(m)$. Since $\displaystyle \phi(m)$ is even we can write $\displaystyle (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: Aug 31st 2011, 09:51 AM
  2. System of Distinct Representatives
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 30th 2010, 11:58 AM
  3. Primitive roots & Reduced residue system
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: Mar 4th 2010, 05:51 AM
  4. Reduced residue system modulo m
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jan 20th 2010, 08:12 PM
  5. Help with reduced row echelon form/solving system
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Mar 23rd 2009, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum