Proof of equation with gcds

Question

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.

Answer 1

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