Prove that the following inequality holds with the exception of finitely many positive integers $n$: $\sum^{n}_{i=1}\sum^{n}_{j=1}gcd(i,j)>4n^2$.
Problem
Source: MOP 2006 Homework - Black Group
Tags: number theory, greatest common divisor, inequalities, number theory unsolved