1
$\begingroup$

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.

$\endgroup$

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
0
$\begingroup$

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

$S=1+2+3+4$

$S=4+3+2+1$

Summing both equations

$2S=5+5+5+5$

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

$\endgroup$

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