Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does there exist a positive real number $C$ and a positive integer $M$ such that for all $n > M$ we have: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j)\ge Cn^2 \log n$$

This originally appeared as an Olympiad problem in the case of $4n^2$ on the RHS. This case was much simpler; simply let $i$ only range on primes values and one quickly derives a $\omega \left ( n^2 \log \log \frac{n}{\log n} \right )$ bound if I didn't mess up. The motivation for above bound is derived from the fact that $$\sum_{j=1}^n \gcd(i,j) \approx \frac{n}{i} \sum_{d|i} \varphi(i/d) \cdot d \approx n \cdot \tau(i) \cdot \frac{6}{\pi^2}$$ So we have: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j) \approx \frac{6n^2}{\pi^2} \sum_{i=1}^n \frac{1}{i} \approx \frac{6}{\pi^2} n^2 \log n$$

However, this is pretty unrigorous reasoning. Does anybody have any ideas as to how to rigorously prove this bound? Of course, showing that the sum in fact gets "close" to $\frac{6}{\pi^2} n^2 \log n$ as $n \to \infty$ would be even better.

share|cite|improve this question
up vote 9 down vote accepted

\begin{align} \sum_{i=1}^{n}{\sum_{j=1}^{n}{\gcd (i, j)}}& =2\sum_{1 \leq j \leq i \leq n}{\gcd (i, j)}-\sum_{i=1}^{n}{\gcd(i, i)} \\ & =2\sum_{i=1}^{n}{\sum_{d \mid i}{\varphi{\left(\frac{i}{d}\right)}d}}-\frac{n(n+1)}{2} \\ & =2\sum_{d=1}^{n}{d\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}{\varphi{(k)}}}-\frac{n(n+1)}{2} \\ & =2\sum_{d=1}^{n}{d(\frac{3}{\pi^2}\left\lfloor \frac{n}{d}\right\rfloor^2+O(\left\lfloor \frac{n}{d}\right\rfloor \log(\left\lfloor \frac{n}{d}\right\rfloor)))}+O(n^2) \\ & =2\sum_{d=1}^{n}{d((\frac{3}{\pi^2}(\frac{n}{d})^2+O(\frac{n}{d}))+O(\frac{n}{d} \log (\frac{n}{d})))}+O(n^2) \\ & =\frac{6n^2}{\pi^2}\sum_{d=1}^{n}{\frac{1}{d}}+O(n^2)+O(n^2\log(n)-n\sum_{d=1}^{n}{\log(d)})+O(n^2) \\ & =\frac{6n^2}{\pi^2}(\log n+O(1))+O(n^2)+O(n^2\log(n)-n(n \log n-n+O(1))) \\ & =\frac{6}{\pi^2}n^2\log n+O(n^2) \end{align}

share|cite|improve this answer
Wow, very nice! I feel somewhat silly for not noticing breaking it up into a sum of $ 1 \le j \le i \le n$, but this is very elegant and answers my question perfectly. – dinoboy Mar 10 '13 at 8:58

Lemma: We have that $$\sum_{d\leq x}\frac{\phi(d)}{d^{2}}=\frac{6}{\pi^{2}}\log x+O(1).$$ This follows from the fact that $\sum_{n\leq x}\phi(n)=\frac{3}{\pi^2}x^2 +O(x\log x)$ along with partial summation.

Using the convolution identity $\left(1*\phi\right)(n)=n$, we see that $$\sum_{i,j\leq x}\gcd\left(i,j\right)=\sum_{i,j\leq x}\sum_{d|i,j}\phi(d),$$ and switching the order of summation yields $$\sum_{d\leq x}\phi(d)\sum_{i,j\leq\frac{x}{d}}1=\sum_{d\leq x}\phi(d)\left[\frac{x}{d}\right]^{2}.\ \ \ \ \ \ \ \ \ \ \ \ (1)$$ Expanding out $\left[\frac{x}{d}\right]=\frac{x}{d}-\left\{ \frac{x}{d}\right\},$ we arrive at the desired asymptotic $$\sum_{i,j\leq x}\gcd\left(i,j\right)=x^{2}\sum_{d\leq x}\frac{\phi(d)}{d^{2}}+O(x^2)=\frac{6}{\pi^{2}}x^2\log x+O(x^2).$$

Using the explicit identity in equation $(1)$, with a lot of work we can derive the second term in the asymptotic expansion.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.