∑i=1n∑j=i+1ngcd(i,j)=∑i=1n∑j=1ngcd(i,j)−∑i=1ngcd(i,i)2\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \gcd(i,j)=\dfrac{\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j)-\sum\limits_{i=1}^{n} \gcd(i,i)}{2}i=1∑nj=i+1∑ngcd(i,j)=2i=1∑nj=1∑ngcd(i,j)−i=1∑ngcd(i,i)
