Mfcttrf

My friend gave me yet another challenge.

Show that $sum_a=1^ngcd(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.

Hint: Since we have
$$
P(n)=sum_k=1^n operatornamegcd(n,k)=sum_dmid ndphi(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^frac32 $$

was argued there, with some constant $ale 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 dphi(frac nd)$, since the $d$ gets counted that many times. A change of index $d to frac nd$ gives $nsum_d fracphi(d)d$.

Thus, the sum is equal to $n sum_d fracphi(d)d$. And now all you need to do is note that $fracphi(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 $2sqrt 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 sqrtfrac 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 $2sqrt n$ since $P geq 5$. Thus we may conclude.