4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

Said more simply, since your set is closed under the negation reflection, its non-fixed points $\rm -k\not\equiv k\:$ pair up and contribute zero to the sum, leaving only the sum of its fixed points $\rm - k\equiv k \iff 2k\equiv 0,\ $ so $\rm\ k\equiv 0\ $ if $\rm\: m\:$ is odd, else $\rm\ k \equiv 0,\ m/2$.

See also Gauss's grade-school trick for summing an arithmetic progression.

$\endgroup$
  • $\begingroup$ I will try to absorb this :(. Thank you. $\endgroup$ – Chan Feb 27 '11 at 2:53
  • $\begingroup$ @Chan: Please feel free to ask questions if anything is not clear. I'm happy to elaborate. $\endgroup$ – Bill Dubuque Feb 27 '11 at 2:58
  • $\begingroup$ 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. $\endgroup$ – Chan Feb 27 '11 at 3:06
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Feb 27 '11 at 3:36
  • $\begingroup$ I will next time. Thanks for your feedback. $\endgroup$ – Chan Feb 27 '11 at 5:44
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ambikasaran: Thanks for a great hint. $\endgroup$ – Chan Feb 27 '11 at 2:53
1
$\begingroup$

Clearly $g.c.d(m-1,m) = 1$. Then $\{(m-1)c_{1},(m-1)c_{2},...,(m-1)c_{\phi(m)}\}$ are all relatively prime to m; furthermore, they are mutually incongruent, since $(m-1)c_{i} \equiv (m-1)c_{j} \ \ (mod \ m)$ implies that $c_{i} \equiv c_{j} \ \ (mod \ m)$, by the cancellation law. We may thus pair each $(m-1)c_{i}$ with some $c_{j}$ such that $(m-1)c_{i} \equiv c_{j} \ \ (mod \ m)$, and we note that $c_{j}$ is uniquely defined for each $(m-1)c_{i}$. Then $$(m-1) c_{i} + (m-1)c_{w} \equiv c_{j} + (m-1)c_{w} \ \ (mod \ m) \equiv c_{j} + c_{k} \ \ (mod \ m) $$. Then $$\sum_{l=1}^{\phi(m)} (m-1) c_{l} \equiv \sum_{l=1}^{\phi(m)} c_{l} \ \ (mod \ m)$$. This implie $$2\sum_{l=1}^{\phi(m)} c_{l} \equiv m\sum_{l=1}^{\phi(m)} c_{l} \ \ (mod \ m) \equiv 0 \ \ (mod \ m)$$. If $g.c.d(2,m) = 1$, that is, m is odd, we have $$\sum_{l=1}^{\phi(m)} c_{l} \equiv 0 \ \ (mod \ m)$$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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