i'm afraid that the problem was posted and solved many times

It would be nice of you to provide the past links where it has been discussed. Until then, let's talk about the probelm. We can always move the posts into the older topic

Yes, I'm really interrested to see a nice solution to this problem. It's reallly beautiful.

I remember seeing it at least twice on th forum, and solving it once before.. But you're right: it is nice. Suppose WLOG that $p<q,r$. We have $p|(q^{2r}-1,q^{p-1}-1)=q^{(2r,p-1)}-1|q^2-1$. This means that either $p|q-1$ or $p|q+1$. Assume first that all our primes are odd. Then we can't possibly have $p|q-1$, because then $p|q^r+1\equiv 2\pmod p\Rightarrow p=2$. We thus have $p|q+1$. From $q|r^{(2p,q-1)}-1$ and $p|q+1,p\ne 2$ we get $q|r^2-1\Rightarrow q|r-1$ or $r+1$. Again, we can't have $q|r-1$, so $q|r+1$. Just as above, from the equation $r|p^q+1$ and $q|r+1$ we deduce $r|p+1$. This is a contradiction: since $p,q,r>2$ and $p|q+1,q|r+1,r|p+1$, we must have $p<q<r<p$. This means that $p=2$. If $q$ is odd, we have $r|2^q+1\Rightarrow r|2^{(2q,r-1)}-1|2^2-1=3$ (the last divisibility takes place because $q$ is odd it cannot divide $r$, given that $q|r^2+1$). $r=3,q=5$ follows, and the only solutions $(p,q,r)$ are the cyclic permutations of $(2,5,3)$. If, on the other hand, $q=2$, then we get $r=5$, and we have the solution $(p,q,r)=(2,2,5)$ and all its cyclic permutations.

I solve it by the order of $p,q,r$ and I think $(2,2,5)$ is one of the answer (when $p=q$) and grobber's solution is very beautiful

Oops! Looks like I missed those solutions the first time. I've edited the message.

Sorry to revive an old thread, but $ (2,2,5)$ is not a solution. It violates $ p|q^r+1$.

MithsApprentice wrote: Find all ordered triples of primes $(p, q, r)$ such that \[ p \mid q^r + 1, \quad q \mid r^p + 1, \quad r \mid p^q + 1. \] Trivially, $ p, q, r $ are all different. WLOG, let $ p $ the smallest. case1) $ p=2 $, $ r \mid 2^q+1 \Rightarrow ord_r2=2 $ or $ 2q $. If $ ord_r2=2 $, $ r \mid 2^2-1=3 \Rightarrow r=3 $. Therefore, $ q \mid 3^2+1=10, q>p \Rightarrow q=5 $. We can check $ (p, q, r)=(2, 5, 3), (5, 3, 2), (3, 2, 5) $ can be answers here. If $ ord_r2=2q $, obviously $ 2q \mid r-1 \Rightarrow r \equiv 1(mod q) $. Therefore, $ q \mid r^2+1 \equiv 1+1=2(mod q) $ which means $ q=2 $, impossible. case2) $ p, q, r \ge 3 $, $ r \mid p^q+1 \Rightarrow ord_rp=2 $ or $ 2q $. If $ ord_rp=2 $, $ r \mid p^2-1=(p-1)(p+1) $. $ r>p-1 $ so $ r \mid p+1, r \ge p+1 \Rightarrow r=p+1 $, impossible. If $ ord_rp=2q $, $ 2q \mid r-1 $ and go on as the same way. We can check this case is also impossible. Therefore, $ (p, q, r)=(2, 5, 3), (5, 3, 2), (3, 2, 5) $ are all of the answers.

grobber wrote: I remember seeing it at least twice on th forum, and solving it once before.. But you're right: it is nice. Suppose WLOG that $p<q,r$. We have $p|(q^{2r}-1,q^{p-1}-1)=q^{(2r,p-1)}-1|q^2-1$. This means that either $p|q-1$ or $p|q+1$. If, on the other hand, $q=2$, then we get $r=5$, and we have the solution $(p,q,r)=(2,2,5)$ and all its cyclic permutations. if you suppose that WLOG that $p<q,r$ then how at end you can write $q=2$ ? and also the solution that obtained in this case is clearly wrong.

The solutions are $(p,q,r) \in \{(2,5,3);(5,3,2);(3,2,5)\}$ We have that this residue system is equivalent to the problem: \[q^r \equiv -1 \; \; (\text{mod} \; \; p), r^p \equiv -1 \; \; (\text{mod} \; \; q),p^q \equiv -1 \; \; (\text{mod} \; \; r) \; \; \]We denote with $x =ord_p(q)$, $y=ord_q(r)$ and $z=ord_r(p)$ Obviously since we are dealing with orders, and we have this neat residue system we get that $x \mid 2r$, $y \mid 2p$ and $z \mid 2q$ So we have some cases The first case is when $x=y=z=2$, from $q^2 \equiv 1\; \; (\text{mod} \; \; p),r^2 \equiv 1\; \; (\text{mod} \; \; q),p^2 \equiv 1\; \; (\text{mod} \; \; r)$ we have that we can set up a system of the following kind: $$q=kp \pm 1$$$$r=tq \pm 1$$$$p=dr \pm 1$$ Which is equivalent to: $$(1-dtk)p=\pm td\pm d\pm 1$$But solving this by a lengthy bash gives no solutions. Second case is when $x=2r$ and $y=z=2$. We have that $x \mid p-1$ and we also have that $p \equiv 1 \; \; (\text{mod} \; \; 2r)$, which we combine with $r^2 \equiv 1 \; \; (\text{mod} \; \;q)$ To get the following: $$p=2tr \pm 1$$$$r=dq \pm 1$$We get that $p=2tdq \pm 2t +1$, from the $r^p \equiv -1 \; \; (\text{mod} \; \; q)$ we get that $(\pm 1)^p \equiv -1 \; \;(\text{mod} \; \; q)$ we have two scenarios: 1.$q=2$, from which we get no solutions. 2.$q > 2$, we get that $r=dq-1$, we use the fact that $p^q \equiv -1 \; \; (\text{mod} \; \; r)$, but this gives us easily that $r=2$, this implies that $dq=3$, obviously $q=3$, and from here we get that $p=4t+1$, and by our starting congruence relations we get that $p=5$, then we permutate to get the other solutions. The third case ($x=2r,y=2p,z=2$) and the fourth case ($x=2r,y=2p,z=2q$) are done in a similar fashion from which we don't get solutions.

mathjmk33 wrote: MithsApprentice wrote: Find all ordered triples of primes $(p, q, r)$ such that \[ p \mid q^r + 1, \quad q \mid r^p + 1, \quad r \mid p^q + 1. \] Trivially, $ p, q, r $ are all different. WLOG, let $ p $ the smallest. case1) $ p=2 $, $ r \mid 2^q+1 \Rightarrow ord_r2=2 $ or $ 2q $. If $ ord_r2=2 $, $ r \mid 2^2-1=3 \Rightarrow r=3 $. Therefore, $ q \mid 3^2+1=10, q>p \Rightarrow q=5 $. We can check $ (p, q, r)=(2, 5, 3), (5, 3, 2), (3, 2, 5) $ can be answers here. If $ ord_r2=2q $, obviously $ 2q \mid r-1 \Rightarrow r \equiv 1(mod q) $. Therefore, $ q \mid r^2+1 \equiv 1+1=2(mod q) $ which means $ q=2 $, impossible. case2) $ p, q, r \ge 3 $, $ r \mid p^q+1 \Rightarrow ord_rp=2 $ or $ 2q $. If $ ord_rp=2 $, $ r \mid p^2-1=(p-1)(p+1) $. $ r>p-1 $ so $ r \mid p+1, r \ge p+1 \Rightarrow r=p+1 $, impossible. If $ ord_rp=2q $, $ 2q \mid r-1 $ and go on as the same way. We can check this case is also impossible. Therefore, $ (p, q, r)=(2, 5, 3), (5, 3, 2), (3, 2, 5) $ are all of the answers. Can you actually suppose WLOG $p$ is the smallest?

Clearly no two primes are equal. WLOG $p$ is minimal. Then write $p\mid q^{2r}-1$ hence $o_p(q)\mid 2r$. This means it is either $2r$ or $2$. Since $p$ is minimal, $2r=o_p(q)\le p-1$ is absurd. Then $p\mid q+1$. Similarly, we get $o_q(r)\mid 2p$. But we also have $o_q(r)\mid q-1$. Note that $\gcd(q-1,2p)\mid \gcd(2q-2,2p)\mid 4$. Then either $q\mid r+1$ or $p=2$. In this case, the conditions are $2\mid q^r+1,q\mid r^2+1,r\mid 2^q+1$. The last condition implies $o_r(2)\mid r-1,2q$ so $\gcd(r-1,2q)\mid \gcd(2r^2-2,2q)\mid 4$, so $q=2$ (absurd) or $r\mid 2+1=3$, that is, $r=3$. Then $q\mid 3^2+1=10$ so since $q=2$ is bad, $q=5$. This extracts cyclic permutations of $(2,5,3)$. So $p\mid q+1$ and $q\mid r+1$. As before, we get $o_r(p)\mid \gcd(r-1,2q)\mid \gcd(2r-2,2q)\mid 4$ so $r\mid p+1$ or $q=2$. We already dealt with permutations of some prime equal to $2$, so then $r\mid p+1$. Since $r> p$ (by minimality), this implies $r=p+1$ so $p=2$ and we have the situation from before.

Clearly, $p,q,r$ must be pairwise distinct. Let $a=\text{ord}_{p}q,b=\text{ord}_{q}r,$ and $c=\text{ord}_{r}p.$ $\textbf{Case 1: }$ One of $a,b,c$ is $2.$ WLOG assume $a=2;$ then $p\mid q^2-1$ but $p\nmid q-1,$ so we must have $p\mid q+1.$ If $p=2,$ then $a\mid 1,$ contradiction. If $q=2,$ then since $p\mid q+1,$ we must have $p=3.$ Now it is easy to check that the only solution is $(p,q,r)=(3,2,5).$ Thus, we may assume $p$ and $q$ are both odd, so $\frac{q+1}{p}$ is even. Then $$r^p\equiv -1\pmod{q}\implies r^{q+1}\equiv 1\pmod{q}\implies r^2\equiv 1\pmod{q}.$$However, if $r\equiv 1\pmod{q},$ then $r^p+1\equiv 2\pmod{q},$ so $q=2,$ contradiction. Hence, $q\mid r+1,$ and we can similarly show that $r\mid p+1.$ Now consider $x=q+1-p,y=r+1-q,$ and $z=p+1-r.$ Since $p\mid q+1,$ we know $p\mid x,$ so $x\ne 1.$ Similarly $y,z\ne 1.$ But $x+y+z=3,$ so we must have (WLOG) $x=3,y=z=0.$ This implies that $p=3,q=5,r=4,$ contradiction. $\textbf{Case 2: }$ $a,b,c\ne 2$ Note that $$q^r\equiv -1\pmod{p}\implies q^{2r}\equiv 1\pmod{p}\implies a\mid 2r, a\nmid r.$$Therefore, since $a\ne 2,$ we must have $a=2r.$ Then by Fermat's Little Theorem, $2r\mid p-1,$ and similarly $2p\mid q-1$ and $2q\mid r-1.$ But this is absurd, as $2r+2p+2q>(p-1)+(q-1)+(r-1).$ We can now conclude that the only solutions are $(p,q,r)=(3,2,5)$ and cyclic rotations.

Brings Satisfaction!

Notice $p,q,r$ are distinct as $p=q$ would imply $p\mid p^r+1,$ or $p\mid 1.$ Lemma: If one of $p,q,r$ is even, then the only solutions are $(2,3,5)$ and permutations. Proof. WLOG let $p=2.$ Then, $q\mid r^2+1$ and $r\mid 2^q+1.$ Hence, $r^2+1=qk,$ where $k$ is even and $-1\equiv 2^q\pmod{r}.$ Raising to the $k$th power yields $$1\equiv (-1)^k\equiv 2^{qk}\equiv 2^{r^2}\cdot 2\equiv (2^r)^r\cdot 2\equiv 4\pmod{r}$$by FLT. Therefore, $r=3$ and $q\mid 10$ so $q=5.$ $\blacksquare$ From $p\mid q^r+1,$ we see $q^{2r}\equiv (-1)^2\equiv 1\pmod{p}.$ Hence, $\operatorname{ord}_p(q)=1,2,r,2r.$ Clearly, $\operatorname{ord}_p(q)=r$ is impossible. Case 1: $\operatorname{ord}_{p}(q)=1.$ This implies $q\equiv 1\pmod{p}.$ Since $1\equiv 1^r\equiv q^r\equiv -1\pmod{p},$ we conclude $p=2$ and our lemma finishes. Similarly, if $\operatorname{ord}_{q}(r)=1$ or $\operatorname{ord}_{r}(p)=1,$ then one of $p,q,r$ is even. Case 2: $\operatorname{ord}_{p}(q)=2r.$ Then, $r\mid 2r\mid p-1$ so $p\equiv 1\pmod{r}.$ But $p^q\equiv -1\pmod{r}$ from $r\mid p^q+1,$ which is absurd. Notice if any of $\operatorname{ord}_{p}(q),\operatorname{ord}_{q}(r),\operatorname{ord}_{r}(p)$ are $1$ or $2r,$ the only solutions are permutations of $(2,3,5).$ Hence, for any new solutions, the orders must all be $2.$ Case 3: $\operatorname{ord}_{p}(q)=\operatorname{ord}_{q}(r)=\operatorname{ord}_{r}(p)=2.$ Notice $q\equiv -1\pmod{p}$ so $p\mid q+1.$ Assuming $p,q,r$ are odd (to find new solutions), we know $p\neq q+1$ so $2p\le q+1.$ Similarly, $2q\le r+1$ and $2r\le p+1.$ Adding yields $2(p+q+r)\le p+q+r+3,$ a contradiction as $p,q,r>2.$ Hence, our only solutions are $(p,q,r)=(2,3,5)$ and permutations. $\square$

Observe that $p, q, r$ are distinct. WLOG $p \leq q \leq r$, and assume they are odd primes (we will deal with $p=2$ later.) Analyzing the first congruence, either $p \mid q+1$ or $r \mid p-1$. But the second constraint is clearly impossible as it implies $$p^q + 1 \equiv 2 \pmod r,$$contradiction as we have odd primes. But this means that $p \leq q+1$ and cyclic permutations, which is obviously impossible by distinctness. As a result, assume $p = 2$. Then $q \mid r^2 + 1$ and $r \mid 2^q + 1$. On the other hand, this means that $q \mid r-1$ or $r = 3$, the former case being clearly impossible. As a result, only $(2, 3, 5)$ works in this case, which describes all solutions up to cyclicity.

Observe that $p, q, r$ are distinct. WLOG $p \leq q \leq r$, and assume they are odd primes (we will deal with $p=2$ later.) Analyzing the first congruence, either $p \mid q+1$ or $r \mid p-1$. But the second constraint is clearly impossible as it implies $$p^q + 1 \equiv 2 \pmod r,$$contradiction as we have odd primes. But this means that $p \leq q+1$ and cyclic permutations, which is obviously impossible by distinctness. As a result, assume $p = 2$. Then $q \mid r^2 + 1$ and $r \mid 2^q + 1$. On the other hand, this means that $q \mid r-1$ or $r = 3$, the former case being clearly impossible. As a result, only $(2, 3, 5)$ works in this case, which describes all solutions up to cyclicity.

1. Assume all odd primes. Also assume distinct. 2. Order of $q$ mod $p$ is $2$ or $2r$. 3. So $2r\mid p-1$ in the latter case, but (I didn't figure out this part until a while later) this can't happen as $p\equiv 1\pmod 2r$ and this violates the third condition. 4. Let's say $p=2$, then $q,r$ are clearly odd. Once again we should get $r=2^2-1=3$ and then $q=5$, and solutions are $(2,5,3)$ and cyclically.

We claim that the only solutions are the cyclic permutations of $(p, q, r) = (2, 5, 3)$. Checking, these work. Suppose that at least one of the three primes is $2$. Without loss of generality, let $p = 2$. Then, $2 \mid (q^r + 1)$, so $q$ is odd. We have $r^2 \equiv -1 \pmod{q}$ and $2^q \equiv -1 \pmod{r}$. Let $z = \operatorname{ord}_r(2)$. Since $2^{2q} \equiv 1 \pmod{r}$, then $z \mid 2q$, but $z \nmid q$. So, $z = 2$ or $z = 2q$. If $z = 2$, then $2^2 \equiv 1 \pmod{r}$, i.e. $r = 3$. This gives us $q \mid (3^2 + 1)$, so $q = 5$. First, assume $z = 2q$. By Fermat's Little Theorem, $2^{r - 1} \equiv 1 \pmod{r}$, so $2q \mid (r - 1)$ implying that $r \equiv 1 \pmod{q}$. Combining this with $r^2 \equiv -1 \pmod{q}$, we get that $q = 2$, which contradicts $q$ being odd. So, the only possible solutions when at least one of the three primes is $2$ is any cyclic permutation of $(p, q, r) = (2, 5, 3)$. Now, assume that all three primes are odd. Consider the first condition: $p \mid (q^r + 1)$. Let $x = \operatorname{ord}_p(q)$. Since $q^r \equiv -1 \pmod{p}$, then $q^{2r} \equiv 1 \pmod{p}$. So, $x \mid 2r$ but $x \nmid r$ so $x = 2$ or $2r$. If $x = 2r$, then by Fermat's Little Theorem, $q^{p - 1} \equiv 1 \pmod{p}$, so $2r = x \mid (p - 1)$. This implies that $p \equiv 1 \pmod{r}$, impossible because $p^q \equiv -1 \pmod{r}$ and $r$ is odd. Thus, $x = 2$. Then $q^2 \equiv 1 \pmod{p}$, but $q \not \equiv 1 \pmod{p}$, so $p \mid (q + 1)$. Since $q + 1$ is even, $2p \mid (q + 1)$. Considering the cyclic permutations, we get that $2p \le q + 1$ and $2q \le r + 1$ and $2r \le p + 1$, clearly impossible. Thus, this case generates no solutions.

We claim that the solutions to these systems is the set of cyclic permutations of $\boxed{(2, 3, 5)}$. Observe that there can be at most one even prime among $p, q, r,$ if any are to exist. Now observe the following: \[q^r + 1 \equiv 0_{(p)} \implies q^{2r} \equiv 1_{(p)} \implies o(q)_p \in \{1, 2, r, 2r\}.\]Case 1: $\left(o(q)_p = 1 \right).$Then $q^r \equiv -1 \pmod p$, but $q^r \equiv 1 \pmod p \implies p = 2$. Case 2: $\left(o(q)_p = 2 \right).$ Then $q^2 \equiv 1 \pmod p \implies p \mid (q - 1)(q + 1)$, and $p$ cannot divide both or else we just obtain $p = 2$ again. Hence $p$ divides either $q - 1$ or $q + 1$. If $p$ divides $q - 1$, we obtain the same result, so $p \mid q + 1$. Case 3: $\left(o(q)_p = r \right).$ Then $q^r \equiv 1 \pmod p$, and $q^r \equiv -1 \pmod p$, so we obtain the same result. Case 4: $\left(o(q)_p = 2r \right).$ Then $q^{2r} \equiv 1 \pmod p \implies p \mid (q^r - 1)(q^r + 1)$. Now $p$ cannot divide both or else we just obtain $p = 2$ again. Hence $p$ divides either $q^r - 1$ or $q^r + 1$. If $p$ divides $q^r - 1$, we obtain the same result, so $p \mid q^r + 1$. However, we then also have $2r \mid p - 1 \implies r \mid p - 1 \implies r \mid p^q - 1$, and also $r \mid p^q + 1 \implies r = 2$. This however may be symmetrically applied to $p = 2$, and so we dismiss this case for further casework below. Assume now that all $p, q, r$ are odd. Then from CASE 2, $p \mid q + 1, q \mid r + 1, r \mid p + 1$. However $p \neq q + 1, q$, as both of these results end in contradictions. Hence $p < q, q < r, r < p$, which is a contradiction. Therefore exactly one of $p, q, r$ must be even. Without loss of generality, let $p = 2$. Then \begin{align*} &q \mid r^2 + 1; \text{ and, } r \mid 2^q + 1. \\ \implies &o(r)_q \in \{1, 2, 4\}; \text{ and } o(2)_r \in \{1,2, q, 2q\} \\ \implies &o(r)_q \neq 1, 2, \text{ but } \boxed{o(r)_q = 4} \text{ could work}; \text{ and } o(2)_r \neq 1, 2 \text{ but } \boxed{o(2)_r = 2, 2q} \text{ could work. }\\ \end{align*}Now $o(r)_q = 4$ gives us $q \mid r^2 + 1$ and $4 \mid q - 1$ (but we really never use this second in this solution). If $o(2)_r = 2$, then $2^2 \equiv 1\pmod r \implies \boxed{r = 3} \implies q \mid 3^2 + 1 \implies \boxed{q = 5}$. If $o(2)_r = 2q$, then $2q \mid r - 1 \implies q \mid r^2 + 1 - (r - 1)(r + 1) = 2$, which is a contradiction. Therefore the only solutions are $\boxed{(p, q, r) \in \{(2, 5, 3), (3, 2, 5), (5, 3, 2)\}}$. $\blacksquare$

We claim that $$(p,q,r) = (2,5,3), (3,2,5), (5,3,2)$$are the only solutions. These work, so we show they are the only ones. First, suppose one of the primes is $2$. WLOG, $p=2$. It follows that $2^q + 1 \equiv 0 \pmod r$, so $$\begin{cases} 2^q \equiv -1 \pmod r \\ 2^{2q} \equiv 1 \pmod r.\end{cases}$$Let $a=\mathrm{ord}_r(2)$. Since $a \nmid q$ while $a \mid 2q$ and $q$ is odd (as $q^r \equiv -1 \pmod 2$), we must have either $a=2$ or $a=2q$. If $a=2q$, it follows that $$2q \mid r-1$$so $r \equiv 1 \pmod q$. Then, $r^p+1 \equiv 2 \equiv 0 \pmod q$, so $q=2$, absurd. If $a=2$, we have $2^2 \equiv 1 \pmod r$, so $r=3$. The second divisibility condition then yields $$q \mid 3^2+1$$and $q$ is odd so $q=5$. Taking cyclic permutations then gives the other $2$ solutions. Now, WLOG suppose $p \geq q \geq r > 2$. We know that $$\begin{cases} q^r \equiv -1 \pmod p \\ q^{2r} \equiv 1 \pmod p \end{cases}$$so letting $\mathrm{ord}_p(q) = a$, we can similar to above obtain $a=2r$ or $a=2$. If $a=2r$, we again have $2r \mid p-1$, so $p \equiv 1 \pmod r$ which gives $r=2$ by the last condition, absurd. Thus, $q^2 \equiv 1 \pmod p$, so $$(q-1)(q+1) \equiv 0 \pmod p.$$We cannot have $q \equiv 1 \pmod p$ since that violates the minimality of the order $2$, so $p \mid q+1$. This implies that $$q \leq p \leq q+1$$so either $p=q+1$ or $p=q$. The former is impossible since $p,q > 2$, while the latter suggests that $p \mid p^r+1$, which is absurd as well, so we are done. $\blacksquare$

Hint or more of a overview of solution as I am lazy and don't wanna type full solution. Basically assume all odd then orders this will give contradictions so atleast one will be 2 Let any one be 2 get (2,3,5) and all rotations. If more than one is 2 then we get 2|odd impossible so done. (p,q,r)= (3,2,5) And all cyclic rotations