Math Olympiad Second Stage Training Camp, 2015

All solutions are $(p, x, y) \in \{(3, 2, 5), (3, 5, 2)\} \cup \{(2, n, 2^k - n) \mid 0 < n < 2^k\}$.

(1) When $p=2$, clearly all $(x,y)$ whose sum is a power of $2$ satisfy the problem's conditions, so we only need to consider $p > 2$.

(2) Suppose $x^{p-1} + y = p^a$ and $x + y^{p-1} = p^b$. Without loss of generality, we assume $x \le y$, and hence $a \le b$. We therefore have
$$p^b = y^{p-1} + x = (p^a - x^{p-1})^{p-1} + x$$
Taking both sides of the above equation modulo $p^a$, and noting that $p-1$ is even, we thus have
$$0 = x^{(p-1)^2} + x \quad \mathrm{mod}\ p^a \qquad (1)$$
If $p \nmid x$, then $x^{(p-1)^2-1} + 1$ is clearly not divisible by $p$, but this contradicts Eq. (1) (since $x \le x^{p-1} < p^a$.)
Hence $p$ does not divide $x$, that is,
$$p^a \mid x^{(p-1)^2-1} + 1 = x^{p(p-2)} + 1.$$

(3) By Fermat's little theorem, $x^{(p-1)^2} = 1 \mod p$, so
$$x + 1 = x + x^{(p-1)^2} = x(1 + x^{(p-1)^2-1}) = 0 \mod p,$$
that is, $p \nmid x + 1$. Let $p^r$ be the highest power dividing $x + 1$.

(4) Now let us consider the highest power dividing $x^{p(p-2)} + 1$. Let us expand $x^{p(p-2)} = (x + 1 - 1)^{p(p-2)}$ binomially as a sum of a series of terms in $(x+1)^k$. For all terms with $k \ge 3$, by the above it must be divisible by $p^{3r}$. The $k=2$ term is
$$-\frac{p(p-2)(p^2-2p-1)}{2}(x+1)^2,$$
which is clearly divisible by $p^{2r+1}$. The $k=1$ term is
$$p(p-2)(x+1),$$
which is clearly divisible by $p^{r+1}$, but not by $p^{r+2}$ (since $r$ is the highest power dividing $x+1$). The last term is $-1$. Combining the above discussion: we know that the highest power dividing $x^{p(p-2)} + 1$ is $p^{r+1}$.

(5) But on the other hand, we assumed from the start that $p^a \mid x^{p(p-2)} + 1$, so we must have $a \le r+1$. But at the same time,
$$p^r \le x+1 \le x^{p-1} + y = p^a \quad (2)$$
so we must have $a=r$ or $a=r+1$.

(6) If $a=r$, then all equalities in Eq. (2) must hold, so $x=y=1$, but this clearly contradicts $p>2$, so $a=r+1$. Furthermore, based on $p^r \le x+1$, we have
$$x = \frac{x^2 + x}{x+1} \le \frac{x^{p-1} + y}{x+1} = \frac{p^a}{x+1} \le \frac{p^a}{p^r} = p.$$
Combining this with $p|x+1$, we have $x = p-1$; in other words, $r=1, a=2$.

(7) Now, if $p \ge 5$, we have
$$p^a = x^{p-1} + y > (p-1)^4 = (p^2 - 2p + 1)^2 > (3p)^2 > p^2 = p^a$$
a contradiction! Hence $p=3$, so $x=p-1=2$, and $y = p^a - x^{p-1} = 5$.