The number of summands $\phi(n)$
If $n$ is a positive integer such that the sum of all positive integers $a$ satisfying $1\leq a\leq n$ and $\gcd(a,n)=1$ is equal to $240n$ then the number of summands namely $\phi(n)$ is
- 120
- 124
- 240
- 480
My attempt:
If $n $= $p_1^{q_1}p_2^{q_2}...p_k^{q_k}$ where $p_1, p_2,...p_k$ are primes.
$240 n = \frac{n(n+1)}{2} - \frac{p_1^{q_1+1}-1}{p_1 -1}\frac{p_2^{q_2+1}-1}{p_2 -1}... \frac{p_k^{q_k+1}-1}{p_k -1} +1 $
From here, I was not able to proceed. Guesswork tells me that the number has to be 480 because the sum is $240n$.
Note that $a$ and $n$ are relatively prime if and only if $n-a$ and $n$ are relatively prime.
Call such a pair $\{a,n-a\}$, where $a$ is relatively prime to $n$, a couple. The sum of the numbers in a couple is $n$.
If $n\gt 2$, there are $\frac{\varphi(n)}{2}$ couples. For every $a$ relatively prime to $n$ gets coupled with someone other than herself.
It follows that our sum is $n\cdot\frac{\varphi(n)}{2}$. If this is $240n$, then $\varphi(n)=480$.