This question already has an answer here:

I am stuck with the following problem that says:

If $n$ is a positive integer such that the sum of all positive integers $a$ satisfying $1 \le a \le n$ and GCD $(a,n)=1$ is equal to $240n,$ then the number of summands ,namely,$\phi(n),$ is

  1. $120$
  2. $124$
  3. $240$
  4. $480$

MY TRY: Just for understanding, if I take $n=5,$then $a_i$'s such that gcd $(a_i,5)=1$ and $\sum a_i=240\times 5$. But, $a_i$'s can only be $1,2,3,4$ ,since $n=5$. Now, I do not know which way to go.

Can someone explain? Thanks in advance for your time.


marked as duplicate by Clément Guérin, Joel Reyes Noche, Najib Idrissi, Claude Leibovici, user91500 Dec 17 '15 at 9:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ Hint: $\gcd(a,n) = \gcd(n-a,n)$. $\endgroup$ – Daniel Fischer Jul 3 '14 at 12:37
  • $\begingroup$ still not sure how to utilize the hint.. $\endgroup$ – learner Jul 3 '14 at 12:47
  • 1
    $\begingroup$ You group the numbers you sum in pairs. $\endgroup$ – Daniel Fischer Jul 3 '14 at 12:48
  • $\begingroup$ If the sum is $240n$, then $n$ must be larger than $240$. The sum is always at most $\sum_{a=1}^{n-1} a = \frac{n(n-1)}{2}$ (except for $n = 1$). Nevertheless, looking at the corresponding sum for smaller $n$ can help. But you should take composite $n$ to get a real understanding of what's going on, for $n$ prime, $\gcd(a,n) = 1$ is not much of a restriction (it only pushes $n$ out of the sum, so the sum is $\frac{n(n-1)}{2}$). $\endgroup$ – Daniel Fischer Jul 3 '14 at 13:08

Maybe this will help drive some of the comments home. You mentioned trying $n=5$. That sum would be



Summing both equations


Does this help? Try for composite values of $n$ if necessary.


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