South African Mathematical Olympiad Third Round

We distinguish two different cases:

Case 1: $\text{gcd}(x, p) = 1$. In this case, $x$ and $x^{k-1} + p$ do not have a common divisor (other than 1) either, and it follows from the factorisation
$$x(x^{k-1} + p) = y^k$$
that both $x$ and $x^{k-1} + p$ have to be $k$th powers, say $x = u^k$ and $x^{k-1} + p = v^k$. Then it follows that
$$p = v^k - u^{k(k-1)} = (v - u^{k-1}) (v^{k-1} + v^{k-2}u^{k-1} + \dots + u^{(k-1)^2}).$$
Both factors have to be positive, and it is clear that
$$v - u^{k-1} < v \le v^{k-1} \le v^{k-1} + v^{k-2}u^{k-1} + \dots + u^{(k-1)^2},$$
so since $p$ is given to be a prime number, we must have $v-u^{k-1} = 1$ and thus $v = u^{k-1}+1$.
Then
$$p = (u^{k-1} + 1)^{k-1} + (u^{k-1} + 1)^{k-2} u^{k-1} + \dots + u^{(k-1)^2}.$$
The right hand side is an increasing function of $u$, so there is at most one value of $u$ which satisfies the equation. If there is such an integer $u$, then there is only one corresponding $v$ and thus only one solution $(x, y)$.

Case 2: $\text{gcd}(x, p) = p$. Then $x^k + px$ has to be divisible by $p$, which implies that $y^k$, and thus $y$, is divisible by $p$ as well. It follows that $x^k$ and $y^k$ are divisible by $p^k$, hence this has to be the case for $px$ as well, so $x = p^{k-1}u$ for some integer $u$. Since $y$ is divisible by $p$, we can also set $y = pv$ to obtain
$$p^{k(k-1)}u^k + p^k u = p^k v^k$$
so that $v$ would have to lie between the two consecutive integers $p^{k-2}u$ and $p^{k-2}u + 1$, an obvious contradiction.
We conclude that there is always at most one solution $(x, y)$.

Since $x^k + px = y^k$, we define $\alpha$ as the difference between $x$ and $y$. Then
$$x^k + px = (x + \alpha)^k > x^k + \alpha x \quad \Rightarrow \quad \alpha < p.$$
In addition
$$\alpha|(x + \alpha)^k - x^k = px \quad \Rightarrow \quad \alpha|x.$$
On the other hand, by binomially expanding $(x + \alpha)^k$, every term (except $\alpha^k$) in the equation is divisible by $x$, therefore $x|\alpha^k$. Let $\beta = \alpha^k/x$ – we will show that $\beta = 1$.
$$\begin{aligned} px &= (x + \alpha)^k - x^k \\ \beta^k px &= (\beta x + \beta \alpha)^k - (\beta x)^k \\ \beta^{k-1} p \alpha^k &= (\alpha^k + \beta \alpha)^k - (\alpha^k)^k \\ \beta^{k-1} p &= (\alpha^{k-1} + \beta)^k - (\alpha^{k-1})^k \end{aligned}$$
However, since $\alpha|x$, $x|\alpha^k$ and $x\beta = \alpha^k$, we have $\beta|\alpha^{k-1}$. This means that every term on the right hand side is divisible by $\beta^k$, and the left is only $p\beta^{k-1}$. So either $p = \beta$, in which case we require
$$y^k = (x + \alpha)^k = x^k + px = x^k + \alpha^k,$$
which has no solutions for $x > 0$, or $\beta = 1$, in which case $x = \alpha^k$. The equation can then be written as $p = (\alpha^{k-1} + 1)^k - (\alpha^{k-1})^k$, and as the right hand side is a strictly increasing function of $\alpha$, for a given $p$ and $k$ there can be at most one solution.