Why is there always a multiplicative function $g$ such that $\sum\limits_{k=1}^n f(\gcd(n,k)) = \sum\limits_{d\mid n} f(d)g(\tfrac{n}{d})$? Please, help me to prove that there is a multiplicative arithmetical function $g$ such that 
$$\sum_{k=1}^n f(\gcd(n,k)) = \sum_{d\mid n} f(d)g(\tfrac{n}{d})$$ for every arithmetical function $f$.
This Example is in textbook : Introduction Number Theory. TOM.M.APOSTOL.
By dividing case, the left sum term can be expressed as 
$$\sum_{(n,k)=1} f((n,k)) + \sum_{(n,k)>1} f((n,k))$$ and we can know that the first term is equal to $\phi(n)f(1)$.
And how can I do later?
 A: We have $$\sum_{k=1}^{n}f\left(\left(n,k\right)\right)=\sum_{d\mid n}f\left(d\right)\sum_{\underset{{\scriptstyle \left(k,n\right)=d}}{k=1}}^{n}1
 $$ and now note that $$\sum_{\underset{{\scriptstyle \left(k,n\right)=d}}{k=1}}^{n}1=\sum_{\underset{{\scriptstyle \left(k/d,n/d\right)=1}}{k/d\leq n/d}}1=\phi\left(\frac{n}{d}\right)
 $$ where $\phi\left(n\right)
 $ is the Euler totient function. Hence $g=\phi
 $ and $$\sum_{k=1}^{n}f\left(\left(n,k\right)\right)=\sum_{d\mid n}f\left(d\right)\phi\left(\frac{n}{d}\right).
 $$ 
A: Hint. As $k$ ranges from $1$ to $n$, what are the possible values of $(n, k)$ (in terms of $n$)?
Update. Since another answer was posted, I'll answer my hint.
The possible values of $(n, k)$ are precisely all the divisors of $n$. Indeed, by definition, $(n, k)$ is a divisor of $n$; and if $d \ge 1$ divides $n$ then $1 \le d \le n$ so taking $k = d$ gives $(n, k) = d$. 
You had the right idea to break up the sum into  $(n, k) = 1$ and $(n, k) > 1$, but really you have to break up the sum further, one sum for each divisor $d$ of $n$, each sum over $k$ such that $(n, k) = d$. The rest of the solution follows Marco Cantarini's.
