4
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

$\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.