Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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$

share|cite|improve this answer
Ambikasaran: Thanks for a great hint. – Chan Feb 27 '11 at 2:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.