0
$\begingroup$

Given that $n$ is a positive integer, we have to find the sum of all the positive integers less than $2n$ and relatively prime to $n$.

I know that when we solve it for numbers $<n$ we get the answer as $\frac{n}{2}*\phi(n)$ where $\phi()$ is the Euler totient function.

I think it will depend on $n$ being even/odd since the factor of 2 will eliminate some numbers since the sum of those relatively prime to $2n$ is $n*\phi(n)$ and all these will be odd. We will have to consider the even numbers too which might be co-prime to $n$ but were obviously not considered for $2n$.

Any help would be appreciated.

$\endgroup$
2
  • $\begingroup$ Suppose $1 \leq d \leq n$ and gcd$(d,n) = 1.$ What can you say about the gcd$(n+d,n)$? Similarly, if gcd$(n+d,n) = 1$, then what can you say about gcd$(d,n)$? $\endgroup$ Sep 30 at 8:47
  • $\begingroup$ @user2661923 It will also be $1$ due to Euclid's algorithm. $\endgroup$ Sep 30 at 8:53
2
$\begingroup$

An intuitive justification for the $\frac n2 \phi(n)$ result is that any integer $m$ in $(0,n]$, which is coprime to $n$, can be paired with $n-m$, which is also coprime to $n$, and their average is $\frac n2$. (For $n>2$ we do not need to worry about pairing $\frac n 2$ with itself because either $n$ is odd and $\frac n 2$ is not an integer, or $n$ is even and $\frac n 2>1$ divides $n$. For $n=2$ we get $1$, which is what $\frac n2 \phi(n)$ would suggest.)

Similarly, each $m$ in $(n,2n]$ can be paired with $m-n$ with $0<m-n\le n$. $m$ is $n$ larger than $m-n$ and there are $\phi(n)$ of them coprime to $n$, so the sum of these $m$s is $\frac n2 \phi(n)+n\phi(n)$.

Adding in the sum of $\frac n2 \phi(n)$ for terms less than or equal to $n$ and you get $$2n\phi(n).$$

Note that this argument does not work for $n =1$, where you get $1+2=3$.

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