0
$\begingroup$

Let $n \geq 3$ be an integer. Consider $S=\sum\limits_{\substack{i=1 \\ (i,n)=1}}^n i$. I want to show that $n \mid S$.

How do I approach? I am not sure if this can be proved in general, I only checked for some particular values of $n$. I need help to prove it or a counter example to disprove it.

$\endgroup$
2
  • 2
    $\begingroup$ note: if $(i,n)=1$, then $(n-i,n)=1$ $\endgroup$ Aug 1 at 17:01
  • $\begingroup$ Please avoid "do my homework for me"-style questions. For example, simply telling us where you got the problem from or explaining what you tried would be a big step forward! (For further feedback/help with asking questions, you can ask here.) $\endgroup$
    – user1729
    Aug 6 at 11:21
4
$\begingroup$

If $n$ and $i$, are coprime, $n$, and $n-i$ are coprime too.

For every term $i$ in the sum, there will be the term $n-i$ too, so that the sum will be a multiple of $n$.

Further note: You can see that the sum will be equal to $\dfrac{\varphi(n)}{2}\cdot{n}$, because there are $\varphi(n)$ terms in the sum, and $\varphi(n)/2$ pairs that add up to $n$.

Further explanation: In the situation where $n-i = i$, we get $n = 2i$, which means that $i$ isn't coprime with $n$.

$\endgroup$
3
  • 1
    $\begingroup$ I think you should mention the case where $i=n-i$ $\endgroup$ Aug 1 at 17:17
  • 1
    $\begingroup$ Thanks for pointing out. $i$ won't be coprime with $n$ in that case, but it's worth to mention. $\endgroup$
    – by24
    Aug 1 at 17:43
  • $\begingroup$ Try not to answer questions when someone dumps one here, like the above, with no effort. Apart from being against site policy, it is more helpful to get them to do some work themselves (which is why people often ask "what have you tried?"). Also, it is not unlikely that this is their assessed homework or exam, so giving them the complete answer is unfair to the rest of their class. $\endgroup$
    – user1729
    Aug 6 at 11:21

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