# The sum of all the positive integers less than 2n and relatively prime to n

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

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

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