USA IMO 2003

We check that this is a solution: $$2\mid 126=5^3+1,5\mid 10=3^2+1,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\ne q$, and similarly $q\ne r,r\ne 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(\mathrm{mod}p),\text{because }p>2,$$ but $$q^{2r}\equiv (-1{)}^2\equiv 1(\mathrm{mod}p).$$ Let $d$ be the order of $q(\mathrm{mod}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(\mathrm{mod}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⟹p\equiv 1(\mathrm{mod}r)⟹0\equiv p^q+1\equiv 2(\mathrm{mod}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}\text{or}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.