# Another gcd problem

My friend gave me yet another challenge.

Show that $$\sum_{a=1}^{n}{\gcd(n,a)}\leq 2n^{3/2}.$$

I have no idea where to start.

This is known as Pillai's arithmetic function, and I put this inequality in OEIS, and it seems to hold, but I don't know how to construct a proof for this.

• Actually, this function is $O(n^{1+\varepsilon})$. See this paper. – lhf Oct 14 at 14:14

Hint: Since we have $$P(n)=\sum_{k=1}^n \operatorname{gcd}(n,k)=\sum_{d\mid n}d\phi(n/d),$$ we can apply estimates for $$\phi(n/d)$$. More details can be found here:

Pillai's arithmetical function upper bound

A bound

$$P(n) < a n^{\frac{3}{2}}$$

was argued there, with some constant $$a\le 2$$.

Actually, your particular challenge follows from a simple rewrite of the given function in terms of the Euler Totient function. Recall $$\phi(n) = |\{1 \leq a \leq n : \gcd(a,n ) = 1\}|$$.

I present it in steps for easiness.

• Given $$a,b$$, show that $$d= \gcd(a,b)$$ if and only if $$d|a,d|b$$ and $$\gcd(a/d,b/d)= 1$$.

• Conclude for any $$n$$ and $$d$$ divisor of $$n$$ that $$|\{1 \leq j \leq n : \gcd(n,j) = d\}| = \phi(n/d)$$.

• Thus, since the gcd of $$n$$ and anything must be a divisor of $$n$$, we get that the sum is equal to $$\sum_{d | n} d\phi(\frac nd)$$, since the $$d$$ gets counted that many times. A change of index $$d \to \frac nd$$ gives $$n\sum_{d | n} \frac{\phi(d)}{d}$$.

Thus, the sum is equal to $$n \sum_{d | n}\frac{\phi(d)}{d}$$. And now all you need to do is note that $$\frac{\phi(x)}{x} \leq 1$$ for any $$x$$, therefore an upper bound for the sum is $$n$$ times the number of divisors of $$n$$. Can you show that any $$n$$ has less than $$2\sqrt n$$ divisors? This should not be too difficult.

Prove it first for numbers of the form $$2^p3^q$$ where $$p,q \geq 1$$. Recall the number of divisors is then $$(p+1)(q+1)$$. See if you can push through an argument by induction or something here.

For the others, proceed by induction : note that $$1$$ has less than $$2$$ divisors, and the same for any prime which has only $$2$$ divisors. Let us keep them also as base cases anyway.

Let composite $$n$$ be given : divide $$n$$ by its largest prime factor $$P$$, which we assume is $$\geq 5$$ since the other cases have been tackled. Then $$\frac nP$$ has at most $$2 \sqrt{\frac nP}$$ divisors by induction. Now, if a number $$k$$ has $$l$$ divisors, then $$kP$$ has at most $$2l$$ many divisors, the originals plus multiplying a $$P$$ with each one.

Thus, $$n$$ has at most $$4 \sqrt{ \frac nP}$$ divisors, which of course is smaller than $$2\sqrt n$$ since $$P \geq 5$$. Thus we may conclude.

• You don't even need to use induction for the last part. We can just pair up the factors. – user686533 Oct 15 at 4:43
• Oh yes, I see. Anyway, the answer should be fine. – астон вілла олоф мэллбэрг Oct 15 at 5:54