Proof of equation with gcds I was given this problem by a friend and am unable to solve it.
Given $x$ is an even integer, prove that $$\frac{x^3}{2}-x^{5/2} \leq x(x-\gcd(x,1))+x(x-\gcd(x,2))+x(x-\gcd(x,3))+\cdots+x(x-\gcd(x,\frac{x-2}{2}))+x(x-\gcd(x,\frac{x}{2}))\leq \frac{x^3}{2}.$$
I tried it out for 2-12 and indeed it does work. I have not yet tried out an induction proof so that might be possible. However, I am not even able to simplify anything except the last term.
 A: The inequality
$$\frac{x^3}{2}-x^{5/2} \leq x(x-\gcd(x,1))+x(x-\gcd(x,2))+x(x-\gcd(x,3))+\cdots+x(x-\gcd(x,\frac{x-2}{2}))+x(x-\gcd(x,\frac{x}{2}))\leq \frac{x^3}{2}$$
is equivalent to the inequality
$$\frac{x^2}{2}-x^{3/2} \leq (x-\gcd(x,1))+(x-\gcd(x,2))+(x-\gcd(x,3))+\cdots+(x-\gcd(x,\frac{x-2}{2}))+(x-\gcd(x,\frac{x}{2}))\leq \frac{x^2}{2}.$$
Let $x = 2n$. Then it is equivalent to the following inequality:
$$2n^2 - (2n)^{1.5} \leq 2n^2 - \sum_{i=1}^n \gcd(2n,i) \leq 2n^2.$$
It is equivalent to 
$$ 0 \leq \sum_{i=1}^n \gcd(2n,i) \leq (2n)^{1.5},$$
which shows that one of the inequality is trivial. 
We know that $\gcd(2n,i) = \gcd(2n, 2n-i)$ for $i = 1, \ldots, n-1$, and $\gcd(2n,2n) = 2\gcd(2n,n)$. 
Hence, if we show that 
$$ \sum_{i=1}^{2n} \gcd(2n,i) \leq 2(2n)^{1.5},$$
then the right-side inequality is proved. 
Let $\phi$ denote  Euler's phi function.
We can transform the left term by 
\begin{equation} 
\begin{split}
\sum_{i=1}^{2n} \gcd(2n,i) 
& 
= \sum_{d | 2n} d \phi (\frac{2n}{d})
= \sum_{d | 2n} \frac{2n}{d} \phi(d) 
= 2n \sum_{d | 2n} \frac{\phi(d)}{d} \\ 
& 
\leq 2n \sum_{d | 2n} 1 
\leq 2n (2\sqrt{2n}) = 2 (2n)^{1.5}.
\end{split}
\end{equation}
We use the facts that 


*

*If $d$ divides $n$, then the number of $i$ ($1\leq i \leq 2n$) satisfying $\gcd(2n,i) = d$ is $\phi(\frac{2n}{d})$.

*$\sum_{d \mid 2n} 1$, the number of divisors of $2n$ is at most $2\sqrt{2n}$. 


$Q.E.D.$
