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$ Commented Sep 30, 2021 at 8:47
  • $\begingroup$ @user2661923 It will also be $1$ due to Euclid's algorithm. $\endgroup$ Commented Sep 30, 2021 at 8:53

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .