# Reduced system of representatives

• Nov 29th 2007, 04:28 PM
AgentNXP
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.
• Dec 5th 2007, 07:43 PM
ThePerfectHacker
Quote:

Originally Posted by AgentNXP
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.