# Show that if $c_1, c_2, \ldots, c_{\phi(m)}$ is a reduced residue system modulo m, $m \neq 2$ then $c_1 + \cdots+ c_{\phi(m)} \equiv 0 \pmod{m}$

Show that if $c_1, c_2,\ldots, c_{\phi(m)}$ is a reduced residue system modulo $m$, $m \neq 2$, and $m$ is a positive integer, then $c_1 +\cdots+ c_{\phi(m)} \equiv 0 \pmod{m}$

From the problem statement, I only know that $\gcd(c_i, m ) = 1$.
Is there any related theorem that I missed?

A hint would be greatly appreciated.

Thanks,
Chan

-

HINT $\$ It's a special case of Wilson's theorem for groups - see my answer here - which highlights the key role played by symmetry (here a negation reflection / involution). Namely, since your set is closed under negation, its non-fixed points $\rm -k\not\equiv k\:$ pair up and contribute zero to the sum, leaving only the sum of the fixed points $\rm - k\equiv k\ \iff\ 2\:k\equiv 0\:,\$ so $\rm\ k\equiv 0\$ if $\rm\: m\:$ is odd, else $\rm\ k \equiv 0,\ m/2\:$.

Note: this was my answer to a similar question.

-
I will try to absorb this :(. Thank you. – Chan Feb 27 '11 at 2:53
@Chan: Please feel free to ask questions if anything is not clear. I'm happy to elaborate. – Bill Dubuque Feb 27 '11 at 2:58
Thanks for your nice offering! I really appreciated it. To be honest, sometimes I want to ask more, but I was not be able to understand it yet. So I could not even know how to ask. Sorry, I'm not a fast thinker, but I will try harder. – Chan Feb 27 '11 at 3:06
@Chan: It's always a good idea to say something about your background when asking a question, so that replies can be aimed at the appropriate level. Here it would be helpful to know if you know any group theory, or modular arithmetic (congruences), etc. – Bill Dubuque Feb 27 '11 at 3:36
I will next time. Thanks for your feedback. – Chan Feb 27 '11 at 5:44

HINT: If $c_i$ is a reduced residue class, then so is $m-c_i$. (Why?) and $\phi(m)$ is even $\forall m >2$

-
Ambikasaran: Thanks for a great hint. – Chan Feb 27 '11 at 2:53