Обозначим $S(n) = \sum_{k=1}^{n} \gcd(k, n)$. Докажите, что $S(n) = \sum_{d \mid n} d \cdot \varphi\!\left(\dfrac{n}{d}\right)$, и вычислите $S(36)$.