$$ \sum_{i=1}^n gcd(i,n)=\sum_{d\mid n} \sum_{i=1}^n [gcd(i,n)=d] \ =\sum_{d\mid n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(i,n)=1] =\sum_{d\mid n} \varphi(\frac{n}{d})
$$
FIELD NOTES
$$ \sum_{i=1}^n gcd(i,n)=\sum_{d\mid n} \sum_{i=1}^n [gcd(i,n)=d] \ =\sum_{d\mid n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(i,n)=1] =\sum_{d\mid n} \varphi(\frac{n}{d})
$$