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.

  • 1
    $\begingroup$ Actually, this function is $O(n^{1+\varepsilon})$. See this paper. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy