Problem 1670

We check that this is a solution:
$$2 \mid 126 = 5^3 + 1, \quad 5 \mid 10 = 3^2 + 1, \quad 3 \mid 33 = 2^5 + 1.$$
Now let $p, q, r$ be three primes satisfying the given divisibility relations. Since $q$ does not divide $q^r + 1$, $p \neq q$, and similarly $q \neq r, r \neq p$, so $p, q$ and $r$ are all distinct. We now prove a lemma.
Lemma. Let $p, q, r$ be distinct primes with $p \mid q^r + 1$, and $p > 2$. Then either $2r \mid p-1$ or $p \mid q^2 - 1$.
*Proof.* Since $p \mid q^r + 1$, we have
$$q^r \equiv -1 \not\equiv 1 \pmod{p}, \quad \text{because } p > 2,$$
but
$$q^{2r} \equiv (-1)^2 \equiv 1 \pmod{p}.$$
Let $d$ be the order of $q \pmod{p}$; then from the above congruences, $d$ divides $2r$ but not $r$. Since $r$ is prime, the only possibilities are $d = 2$ or $d = 2r$. If $d = 2r$, then $2r \mid p-1$ because $d \mid p-1$. If $d = 2$, then $q^2 \equiv 1 \pmod{p}$ so $p \mid q^2 - 1$. This proves the lemma. ■
Now let's first consider the case where $p, q$ and $r$ are all odd. Since $p \mid q^r + 1$, by the lemma either $2r \mid p-1$ or $p \mid q^2 - 1$. But $2r \mid p-1$ is impossible because
$$2r \mid p-1 \implies p \equiv 1 \pmod{r} \implies 0 \equiv p^q + 1 \equiv 2 \pmod{r}$$
and $r > 2$. So we must have $p \mid q^2 - 1 = (q - 1)(q + 1)$. Since $p$ is an odd prime and $q - 1, q + 1$ are both even, we must have
$$p \mid \frac{q-1}{2} \quad \text{or} \quad p \mid \frac{q+1}{2};$$
either way,
$$p \le \frac{q+1}{2} < q.$$
But then by a similar argument we may conclude $q < r, r < p$, a contradiction.
Thus, at least one of $p, q, r$ must equal 2. By a cyclic permutation we may assume that $p = 2$. Now $r \mid 2^q + 1$, so by the lemma, either $2q \mid r - 1$ or $r \mid 2^2 - 1$. But $2q \mid r - 1$ is impossible as before, because $q$ divides $r^2 + 1 = (r^2 - 1) + 2$ and $q > 2$. Hence, we must have $r \mid 2^2 - 1$. We conclude that $r = 3$, and $q \mid r^2 + 1 = 10$. Because $q \ne p$, we must have $q = 5$. Hence (2, 5, 3) and its cyclic permutations are the only solutions.