>>926
Σ[j=1,n] 2[ij/n] = gcd(i, n) - n + i(n+1)
から従うわけですね