$\sum$ GCD + equation

For this, it is instructive to use the Euler Totient Function and we'll also put $m=n-k$ . We can dive the summation into two parts, one that $p|q$ , in which we'll write $q=p q_1$ , and another part in which this doesn't happen, so the gcd is 1. Concretely, since there are $\phi(p^m)$ terms on the latter term:

$\sum_{q=1}^{p^m}gcd(q,p^m)= \sum_{q_1=1}^{p^{m-1}}gcd(p q_1,p^m)+\phi(p^m) = p \sum_{q_1=1}^{p^{m-1}}gcd(q_1,p^{m-1})+\phi(p^m)$

Now we can use induction on the sum factor to show:

$\sum_{q=1}^{p^m}gcd(q,p^m)= p^m + \sum_{j=1}^{m}p^{m-j}\phi(p^j)$

So now, we use the fact that $\phi(p^j)=p^j-p^{j-1}$ :

$\sum_{q=1}^{p^m}gcd(q,p^m)= p^m + \sum_{j=1}^{m}p^{m-j}(p^j-p^{j-1}) = p^m + \sum_{j=1}^{m}(p^m-p^{m-1})=p^m + m(p^m-p^{m-1})$

Back to the question, we want $p^{m+1}=\sum_{q=1}^{p^m}gcd(q,p^m)=p^m + m(p^m-p^{m-1}) \to m(p^m-p^{m-1})=p^{m+1}-p^m \to \boxed{m=p}$ . Therefore, $\boxed{n=p+k}$

Let's evaluate sum in left part: $\sum _{ q=1 }^{ { p }^{ n-k } }{ \text{gcd}\left( q,{ p }^{ n-k } \right) } ={ p }^{ n-k }+\sum _{ q=0 }^{ n-k-1 }{ \left( \frac { { p }^{ n-k } }{ { p }^{ q } } -\frac { { p }^{ n-k } }{ { p }^{ q+1 } } \right) { p }^{ q } } ={ p }^{ n-k }+\sum _{ q=0 }^{ n-k-1 }{ \left( \frac { { p }^{ n-k }-{ p }^{ n-k-1 } }{ { p }^{ q } } \right) { p }^{ q } } =$ $={ p }^{ n-k }+\sum _{ q=0 }^{ n-k-1 }{ \left( { p }^{ n-k }-{ p }^{ n-k-1 } \right) } ={ p }^{ n-k }+\left( n-k \right) \left( { p }^{ n-k }-{ p }^{ n-k-1 } \right) ,\quad n\ge k;$ $n\ge k$ because ${ \text{gcd}\left( \cdot \right) : Z \to { N } }$ and if $n<k$ then ${ p }^{ n-k }$ non-integer. Solve the equation: ${ p }^{ n-k }+\left( n-k \right) \left( { p }^{ n-k }-{ p }^{ n-k-1 } \right) ={ p }^{ n-k+1 };\\ \left( n-k \right) \left( { p }^{ n-k }-{ p }^{ n-k-1 } \right) ={ p }^{ n-k+1 }{ -p }^{ n-k };\\ \left( n-k \right) \left( { p }^{ n-k }-{ p }^{ n-k-1 } \right) =p\left( { p }^{ n-k }{ -p }^{ n-k-1 } \right) ;$ ${ p }^{ n-k }{ -p }^{ n-k-1 }>0$ , because $p>1$ , so we can divide the two parts of the equation: $n-k=p\Rightarrow \boxed{n=p+k} >k$