# 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.

$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.