Curious number theory problem
Solution 1:
Let $g=\gcd(n,m)$, so that $n=gn_1$ and $m=gm_1$ with $\gcd(n_1,m_1)=1$. Then \begin{equation} k^{m+n} = g^{m+1}n_1m_1^n. \end{equation} There are two cases. First, assume $\gcd(g,n_1)=1$, so $n_1=n_2^{m+n}$. Write $k=n_2k_1$. Now \begin{align} (n_2k_1)^{m+n} &= g^{m+1}n_2^{m+n}m_1^n \\ k_1^{m+n} &= g^{m+1}m_1^n. \end{align} If $\gcd(g,m_1)=1$, then $m+1=m+n$ and $n=m+n$, so $(m,n)=(0,1)$, contradicting $m \in \mathbb{N}$. Hence $h=\gcd(g,m_1)>1$, so $g=hg_1$ and $m_1=hm_2$.
Does that give you enough to go on?