Feels surreal to say that this is the first Indonesia problem on IMO, proposed by yours truly (Valentio Iverson from Indonesia). Pleasantly surprised that it appears as P2! Hope people enjoy this problem as much as I do.

$\text{Very nice problem Valentino}$

Good advanced diophantine practice!

I claim that the only such pair is $(a, b) = (1, 1)$. Indeed, $(a, b) = (1, 1)$ satisfies the problem condition. Claim: $ab + 1$ is a power of 2. Proof. Suppose the exists a prime divisor $2 < p$ that divides $ab + 1$. Then, taking $n \equiv p-2 (p-1)$ and $n > N$, we see that $p \mid a^n + b$ and $p \mid b^n + a$. Therefore, $p \mid g$. Now, taking $n \equiv 0 (p-1)$, we get that $p \mid g = \gcd(a^n + b, b^n + a)$, so by FLT, $p \mid a + 1, p \mid b + 1 \implies p \mid 2$, a contradiction. $\square$ Now suppose $ab + 1 = 2^k$ for some $k \ge 1$. Taking $\nu_2(n)$ large enough and $n > N$, we see that $\nu_2(a^n - 1) > \nu_2(b + 1)$, so $\nu_2(a^n + b) = \nu_2(a^n - 1 + b + 1) = \nu_2(b + 1)$. Similarly, $\nu_2(b^n + a) = \nu_2(a + 1)$. Hence, $\nu_2(g) = \min(\nu_2(a + 1), \nu_2(b + 1))$. Take a positive integer $n$ such that $\nu_2(n + 1)$ large and $n > N$, we see that $\nu_2(a^{n+1} - 1) > k$. Let $M = \nu_2(a^{n + 1} - 1)$, then $a^n + b \equiv \frac{1}{a} + b \equiv \frac{ab + 1}{a} (2^M)$, so $\nu_2(a^n + b) = k$. Analogously, $\nu_2(b^n + a) = k$. This implies $\nu_2(g) = k$. However, $\nu_2(g) = \min(\nu_2(a + 1), \nu_2(b + 1))$, this forces to $k = 1$, as wanted. $\blacksquare$

First note that if $a=b$, we have $(a^n + a, a^n + a) = a^n + a$ which is eventually constant if and only if $a=1$. We may now assume that $a<b$ due to symmetry. Let $d = (a, b)$ with $a = dx$, $b = dy$ and $(x, y) = 1$. We have $$G_n := (a^n + b, b^n + a) = d(d^{n-1}x^n + y, d^{n-1}y^n + x).$$Further, we have $$\frac{G_n}{d} = (d^{n-1}x^n + y, d^{n-1}y^n + x) = (d^{n-1}x^n + y, x^{n+1} - y^{n+1})$$since $$y^n(d^{n-1}x^n + y) - x^n(d^{n-1}y^n + x) = y^{n+1} - x^{n+1},$$noting that the coefficients $x^n$ and $y^n$ are coprime to $G_n/d$ (indeed, if $p$ is a prime dividing both $x$ and $G_n/d$, then $p\mid d^{n-1}x^n + y$ implies that $p\mid y$, but $x$ and $y$ are coprime; similarly if $p$ is a prime dividing both $y$ and $G_n/d$). Now, let $q$ be a positive integer parameter, assumed to be coprime to $x, y$ and $d$, as well as such that $q\nmid x-y$. We would like to force $q\mid d^{n-1}x^n + y$ and $q\mid x^{n+1} - y^{n+1}$ for infinitely many $n$, as well as $q\nmid x^{n+1} - y^{n+1}$ for infinitely many $n$. The latter relation gives $(x/y)^{n+1}\equiv 1\pmod q$ and we can force this to happen by choosing $n+1 = k\phi(q)$ for any positive integer $k$, and force it not to happen by choosing $n+1 = k\phi(q) + 1$, since $q\nmid x-y$. It remains to show that such a positive integer $q$ can be chosen with the additional property that $q\mid d^{n-1}x^n + y$ when $n+1 = k\phi(q)$. We need $$d^{k\phi(q)-2}x^{k\phi(q)-1} + y \equiv 0 \pmod q \iff d^{-2}x^{-1}+y\equiv 0\pmod q\iff q\mid d^2xy + 1.$$Note that such $q$ is automatically coprime to $x, y$ and $d$. To ensure that $q\nmid x-y$, we can take $q=d^2xy + 1$. Indeed, if $x\equiv y\pmod q$, we have $d^2xy + 1\mid x-y$, but $y>x$ by the first paragraph and obviously $d^2xy + 1 > y > y - x$. This finishes the solution, for we have shown that $dq\mid G_n$ for infinitely many $n$ as well as $dq\nmid G_n$ for infinitely many $n$, thus $G_n$ cannot be eventually constant.

Let $q=ab+1$. Then $q \mid a^n+b,b^n+a$ whenever $n \equiv -1 \pmod{\varphi(q)}$, hence $q \mid g$, but then $q \mid a^{n+1}-a^n$ for large $n$ and hence $q \mid a-1$ (since $q$ is clearly coprime to $a$), thus $a=1$ and similarly $b=1$, hence $a=b=1$, which indeed works.

The proposer noted that the main idea is looking at what $ab + 1$ does. Here is another solution, inspired by @above's first step. Edit: I forgot something. The problem has a funny backstory; I'll let the proposer post it if he's willing to First note that $ab + 1$ is coprime with $a$ and $b$. Picking $n$ big enough with $n \equiv -1 \pmod{\phi(ab + 1)}$ gives $ab + 1 \mid a^n + b$ and $ab + 1 \mid b^n + a$, so $ab + 1 \mid g$. In particular, picking $n$ big enough with $n \equiv 1 \pmod{\phi(ab + 1)}$ gives $ab + 1 \mid a + b$. This forces either $a = 1$ or $b = 1$. Finally, WLOG $b = 1$. Then $\gcd(a^n + 1, a + 1)$ is eventually constant. For $n$ odd, it is equal to $a + 1$, so $a + 1 \mid a^n + 1$ for all $n$ big enough. Picking $n$ even gives $a + 1 \mid 2 \implies a = 1$, and thus $g = 2$. Indonesia has made another history! Congratulations to IndoMathXdZ!

Cute! Notice that substituting $n=\varphi(ab+1)t-1$ yields that $ab+1 \mid g$ then $ab+1 \mid a^n+b$ now take $n \equiv 1 (\mod \varphi(ab+1))$ to get either $a=1$ or $b=1$, WLOG $b=1$ then $gcd(a^n+1,a+1)$ is constant for $n \geq N$ for odd $n$ it is $a+1$ while for even it divides $2$, so $a=1$, therefore $a=b=1$ is the only solution. EDIT: sniped by @above

What is the MOHS of this problem?

Let $\gcd(a,b) = k, a= pk$ and $b=qk$, where $p$ and $q$ are coprime. So, we get that $$\gcd(k^{n-1}p^{n+1} + pq, k^{n-1}q^{n+1} + pq) = g_1$$$$\gcd(p^{n+1}-q^{n+1},k^{n-1}q^{n+1} + pq) = g_2$$for some $g_1,g_2 \in \mathbb{N}$ Note that $g_2$ is fixed, thus there exist prime $t$ such that $t \mid g_2$ Consider $p^{n+1} \equiv q^{n+1} \pmod{t}$ $$p^{n+2} \equiv p^{n+1}q \equiv q^{n+1} \pmod{t}$$$$p \equiv q \pmod t$$Consider $k^{n-1}q^{n+1} + pq \equiv 0 \pmod t$ Let $M \leqslant n = \phi{(t)} \Phi + c$,we get that $$k^{c-1}q^{c+1} + pq \equiv 0 \pmod t$$Take $c =1$, $$q^2 + pq \equiv 0 \pmod t$$$$p + q \equiv 0 \pmod t$$thus, $p=q$, which follows $a=b$ So, $a^n + a$ has to be a fixed constant, which gives us only $a=1$. Consequently $(a,b) = (1,1)$

Splendid problem! What makes this problem hard is that one can write 30000 things which seem useful but then when logically realizing what one needs to prove, they get thrown in the bin. Solved with Maths_Girl and I admit that personally would probably not have solved it completely in contest conditions. Step 1: Working with a prime p not dividing a and b is easier - what do we get? Firstly, we show that there does not exist a prime $p \geq 3$ which does not divide $a$ and $b$, but divides $a^n + b$ and $b^n + a$ for all large $n$. Suppose otherwise, then $(-1)^n a^{n^2} + a \equiv 0 \pmod p$. Take $n$ to be even, then $a^{n^2-1} \equiv -1 \pmod p$, so the order of $a$ mod $p$ divides $2n^2 - 2$ for all large $n$. In particular, it divides $2(n+2)^2 - 2 = 2n^2 + 8n + 6$, so it divides $8n+8$ for large even $n$, hence divides $8n+8$ and $8(n+2) + 8 = 8n+24$, i.e. it divides $8$. However, $2n^2-2$ is divisible by $2$, but not by $4$ for all large even $n$, so $a^2 = 1 \pmod p$. Now from $a^{n^2-1} \equiv -1 \pmod p$ for large even $n$ we get $a\equiv -1 \pmod p$. Analogously $b\equiv -1 \pmod p$, but then $n$ odd in $a^n + b$ and $b^n + a$ imply that $p$ must divide $(-1)^n - 1 = -2$, contradiction! Step 2: If we show that there is a prime $p\geq 3$ such that $a^n + b$ and $b^n + a$ are divisible by $p$ for infinitely many $n$, then $(a,b)$ does not work, since $g$ is divisible by $p$ infinitely often, but not always by Step 1. (Realized this is really needed by playing with $a=4$, $b=2$.) We look for a congruence of the form $n\equiv \ ? \pmod p$ where $?$ is a constant in order to apply Fermat's little theorem, for a suitable $p$ dividing an expression of $a$ and $b$. Here $? = 0,1,2$ did not seem to work, but $? = -1$ works! Indeed, $a^{-1} + b$ and $b^{-1} + a$ are divisible by $p$ if and only if $ab+1$ is (and note that if $p$ divides $ab+1$, then $p$ does not divide $a$ and $b$). So if $ab+1$ has a prime divisor $p\geq 3$, then we have obtained a contradiction. Step 3: Take care of $ab+1$ being a power of $2$. Fortunately, we only need that $ab+1$ is divisible by $4$ (unless $a=b=1$, which satisfies the problem conditions). Indeed, we may assume $a\equiv 3 \pmod 4$ and $b \equiv 1 \pmod 4$ and now if $n$ is even, then $a^n + b$ is divisible by $2$, but not by $4$ (and $b^n + a$ is divisible by $4$), while if $n$ is odd, then both $a^n + b$ and $b^n + a$ are divisible by $4$, so $\gcd(a^n+b,b^n+a)$ is infinitely often divisible by $4$ and not divisible by $4$, contradiction. EDIT: Reminded now that the trick with $n\equiv -1 \pmod p$ famously appears in ELMO SL 2014 N7 (and to some rather unrelated extent, in IMO 2005/4).

I heard that people either got nowhere or solve this problem completely, making this a 0/7 problem…

Mathological03 wrote: I heard that people either got nowhere or solve this problem completely, making this a 0/7 problem… I have no idea on the situation, but definitely imagine somebody thinking of doing Step 1 in my solution or similar (cause why not? Typical NT stuff) and then get stuck on Step 2 or not even realizing what to do; this should deserve some reasonable partial.

The answer is $a=b=1$ only. This is easily verified to work. We firstly show that $ab+1$ is a power of $2$. Firstly we observe that $a$ and $b$ are both in $U_{ab+1}$ so we may write \[ a^n + b \equiv a^n - \frac 1a \equiv \frac{a^{n+1} - a}{a} \pmod{ab+1}, \]so picking $n = -1 + k\varphi(ab + 1)$ suffices. But if an odd prime $p$ divides $ab + 1$, then at most one of $a$, $b$ is $1$ mod $p$, since $1 \not \equiv -1 \pmod{p}$. But then not every $n$ will give $p \mid a^n+ b$, a contradiction. So $ab + 1$ is a power of $2$. Now if $4 \mid ab + 1$, then we notice that both $a$ and $b$ are odd, whence $a^2 = b^2 = 1$ mod $4$ and $\{a,b\} \equiv \{3, 4\} \pmod{4}$ (Sorry for the abuse of notation.) But this is bad, as this means that if $2$ divides $n$, then one of $a +1$, $b+1$ is only divisible by $2$, and if $2$ doesn't divide $n$, then $a+b$ is divisible by $4$. So the $\gcd$ is never constant, and we are done.

Assassino9931 wrote: Mathological03 wrote: I heard that people either got nowhere or solve this problem completely, making this a 0/7 problem… I have no idea on the situation, but definitely imagine somebody thinking of doing Step 1 in my solution or similar (cause why not? Typical NT stuff) and then get stuck on Step 2 or not even realizing what to do; this should deserve some reasonable partial. I think Step 1 is not really necessary for the solution. So I wouldn't be so sure it would be worth "some reasonable partial" (but I haven't seen the marking scheme yet).

The answer is $a = b = 1$, which clearly works by setting $N = 7776$ and $g = 2$. Now we prove it's the only solution. Suppose otherwise. Claim: Any prime divisor of $ab + 1$ divides $g$. Proof: Let $p$ be a prime divisor of $ab + 1$. Notice that both $a$ and $b$ are relatively prime to $p$. The result is obvious if $p = 2$ because it implies $a,b$ are both odd, so $a^n + b$ and $b^n + a$ are both even. Now assume $p > 2$. Let $n = N(p-1) - 1 \ge N$. We have\[a^n + b = \frac{a^{n+1} + ab}{a} = \frac{a^{N(p-1)} + ab}{a} \equiv \frac{ab + 1}{a} \equiv 0\pmod p\]Similarly,\[ b^n + a = \frac{b^{n+1} + ab}{b} = \frac{b^{N(p-1)} + ab}{b} \equiv \frac{ab + 1}{b} \equiv 0\pmod p \]Therefore, $p$ divides both $a^n + b$ and $b^n + a$, so $p$ divides $g$. $\square$ Claim: Any prime divisor of $ab + 1$ must divide $a + 1$ and $b + 1$. Proof: Since switching $a,b$ doesn't change the problem, it suffices to show that any prime divisor of $ab + 1$ divides $b + 1$. Let $p$ be a prime divisor of $ab + 1$. Clearly if $p = 2$, then $b$ is odd, so $p\mid b -1 $. Assume $p$ is odd now. By our above claim, $p$ divides $b^n + a$ and $a^n + b$ for all $n \ge N$, so $p$ divides $b^{2n} + a$ and $a^{2n} + b$. Since $b^{2n} + a \mid (b^{2n})^{2n} - a^{2n} = b^{(2n)^2} - a^{2n} $, we have that\[p\mid a^{2n} + b + (b^{(2n)^2} - a^{2n} ) = b(b^{(2n)^2 - 1} + 1) \]Since $p$ doesn't divide $b$, $p$ must divide $b^{(2n)^2 - 1} + 1$ for all $n \ge N$. Now let $n = N(p-1)$. We have that $p \mid b^{4N^2 (p-1)^2 - 1} + 1$, multiplying the RHS by $b$ gives that $p$ divides $b^{4N^2 (p-1)^2} + b \equiv b + 1 \pmod p$, so $p\mid b + 1$. $\square$ Claim: $2$ is the only prime divisor of $ab + 1$. Proof: Clearly $ab + 1 > 1$ must have a prime factor, so let $p$ be a prime divisor of $ab + 1$. We have $p\mid b + 1$, so $p \mid a(b+1) - (ab + 1) = a - 1$, so $p$ divides $a - 1$ and $a + 1$, implying $p = 2$. $\square$ Claim: $4$ cannot divide $ab + 1$. Proof: Suppose otherwise. Then $a,b$ are clearly odd and $ab \equiv 3\pmod 4$. WLOG assume that $a \equiv 1\pmod 4$ and $b \equiv 3\pmod 4$. If $n \ge N$ is a large even number, then $4\nmid b^n + a$ since $b^n$ and $a$ are both $1\pmod 4$, so $4\nmid g$. However, if $n \ge N$ is a large odd number, then $a^n + b \equiv 1^n + 3 \equiv 0\pmod 4$ and $b^n + a \equiv 3^n + 1 \equiv 0\pmod 4$, so $4$ must divide $g$, absurd. $\square$ Thus, $ab + 1 = 2$, implying $a = b = 1$.

This porblem was so easy

khina wrote: Congrats to the proposer! Another tricky point is I think when you try to look at which small numbers divide $g$, a more natural option than $ab + 1$ is $a + b$. Running the analogous argument to the one shown in solutions above gives us that if $\gcd(a, b) = m$ and $a/m = x, b/m = y$, then we have that $x + y$ divides both $a$ and $b$. But this is actually perfectly fine as we can scale $m$ to be whatever we want it to be; I haven't gone further than here, but my impression from students was that this lead to just more and more issues. At least from here one could find a quick way to catch the main idea of the problem! For example, I get stucked with this case and try to find a solution for some particular one. Let me look at $a=6, b=3$, here $a+b$ has the only odd prime divisor $3$ which divides $a,b$ too. I want to find some prime $q\not = 3$ that divides both $6^n+3, 3^n+6$ to got a contradiction. I know that $3^n\equiv -6 \pmod q$, then $2^n(-6)\equiv -3 \pmod q$, hence $2^{n+1}\equiv 1\pmod q$, so I can choose a positive integer $n$ such that $n\equiv -1 \pmod {q-1}$, and prime $q$ such that $3^{-1}+6$ is divisible by $q$.

Today I tried the problem again and found another way to spot the $ab+1$ trick (which I don't see above), so I decided to post this solution along with some comments on my in-contest experience (despite not solving it there).

Answer: $(1,1)$. Proof that answer works: in this case $$\gcd(a^n+b,b^n+a)=2$$for all $n\in\mathbb N$, so $(1,1)$ works. Now we prove that $(a,b)=(1,1)$. Observe that $\gcd(a,ab+1)=\gcd(b,ab+1)=1$. By choosing $n=\varphi(ab+1)N-1$ and using Euler's theorem, we have $$a^n+b\equiv a^{-1}+b\equiv 0\pmod{ab+1}.$$so $ab+1\mid a^n+b$. Similarly $ab+1\mid b^n+a$ so $$ab+1\mid \gcd(a^n+b,b^n+a)=g.$$As a result we have $ab+1\mid a^n+b$ for all $n\ge N$, so $\{a^n\}$ is eventually constant modulo $ab+1$. As $\gcd(a,ab+1)=1$, this implies that $$a\equiv 1\pmod{ab+1}.$$If $a\ne 1$, then $ab+1\le a-1$, which is impossible. Hence $a=1$. Similarly $b=1$ so $(a,b)=(1,1)$.

Did anyone mention that this problem appeared in the IMSC China International camp 2024 and benefitted some students??? (P.S. I am not blaming anyone that a setup has been made; in fact I can assure that no such thing has happened, I am just giving a fun fact here.)

Assassino9931 wrote: Did anyone mention that this problem appeared in the IMSC China International camp 2024 and benefitted some students??? (P.S. I am not blaming anyone that a setup has been made; in fact I can assure that no such thing has happened, I am just giving a fun fact here.) @above I also realized this and I think it's very unfair indeed. It is completely the same idea with completely the same construction. If I recall proposer of that problem was Navid Safaei (forgive me if I'm wrong) . So far I haven't heard of anyone claiming to have known this problem before the IMO though

straight wrote: Assassino9931 wrote: Did anyone mention that this problem appeared in the IMSC China International camp 2024 and benefitted some students??? (P.S. I am not blaming anyone that a setup has been made; in fact I can assure that no such thing has happened, I am just giving a fun fact here.) @above I also realized this and I think it's very unfair indeed. It is completely the same idea with completely the same construction. If I recall proposer of that problem was Navid Safaei (forgive me if I'm wrong) . So far I haven't heard of anyone claiming to have known this problem before the IMO though No, the origin of the problem I put is Ukraine 2019 8.8/9.7 by Arsenii Nikolaev (who was actually Observer B at IMO 2024 if I am not mistaken, so in particular not part of the leaders/observer A problem voting). And, well, I did hear about at least one student benefitting from that, but prefer keep the identity of the country confidential.

We uploaded our solution https://calimath.org/pdf/IMO2024-2.pdf on youtube https://youtu.be/daboPS8Dtyk.

Here is the (primitive root)-styled solution, in spirit of what VicKmath7 wrote above. Let $p \geq 3$ be a prime. Consider firstly the following: when is there an integer $n$ such that $a^n + b \equiv 0 \pmod p$? If $g$ is a primitive root mod $p$ (where $p$ is a prime not dividing $a$ or $b$!), then writing $a \equiv g^A$, $b \equiv g^B$ transfers to the equivalent $g^{B}(g^{nA-B}+1) \equiv 0 \pmod p$, i.e. $nA - B \equiv \frac{p-1}{2} \pmod {p-1}$. Similarly, for $b^n+a$ to be divisible by $p$ we must have $nB - A \equiv \frac{p-1}{2} \pmod {p-1}$. Now if it is the case that $A+B\equiv \frac{p-1}{2} \pmod {p-1}$, then taking $n\equiv -1 \pmod {p-1}$ would work not only for $a^n+b$, but also for $b^n + a$. But note that $A + B \equiv \frac{p-1}{2} \pmod {p-1}$ if and only if $g^{A+B} \equiv -1 \pmod p$, i.e. $p$ divides $ab+1$. Therefore if we initially take $p$ to be an odd prime divisor of $ab+1$ (note that such does not divide $a$ or $b$), then there are infinitely many $n$, for which the required greatest common divisor is divisible by $p$. However, it cannot be the case that $p$ divides $a^n+b$ and $b^n+a$ for all large $n$ -- otherwise, $p$ would divide $a^{n+1} + ab \equiv a^{n+1} - 1$, so $p$ would divide $a-1$ (due to $a^{n+1} \equiv a^{n+2} \equiv 1 \pmod p$ and $\gcd(a,ab+1) = 1$), similarly $p$ would divide $b-1$, but now $ab+1 \equiv 0 \pmod p$ implies that $p$ must also divide $a+1$ and hence $(a+1) - (a-1) = 2$, contradicting $p\geq 3$. Therefore, if $a$ and $b$ are such that $ab+1$ has an odd prime divisor, then they cannot satisfy the problem conditions. Finally, suppose $ab+1$ is a power of $2$. Fortunately, we only need that $ab+1$ is divisible by $4$ (unless $a=b=1$, which satisfies the problem conditions). Indeed, we may assume $a\equiv 3 \pmod 4$ and $b \equiv 1 \pmod 4$ and now if $n$ is even, then $a^n + b$ is divisible by $2$, but not by $4$ (and $b^n + a$ is divisible by $4$), while if $n$ is odd, then both $a^n + b$ and $b^n + a$ are divisible by $4$, so $\gcd(a^n+b,b^n+a)$ is infinitely often divisible by $4$ and not divisible by $4$, contradiction.

What an amazing problem, kudos to the problem proposer $\textbf{Answer:}$ $a=b=1$ Let $p$ be a prime such that $p\mid g$, so $p\mid b^{n-1}(a^n+b)-b^n-a\implies p\mid ab-1$ if $p\nmid a$. Finally checking if $ab+1\mid g$ and choosing $n\equiv -1\pmod{\phi(ab+1)}$(this is possible because $\gcd(ab+1,a)=\gcd(b,ab+1)=1$) we have

The last part comes from the fact that $a,b$ can be inverted modulo ${ab+1}$. Similarly we obtain $b^n+a\equiv 0\pmod{ab+1}$ which gives us $ab+1\mid g\implies p\mid ab+1$ Now we take $n \equiv 0 \pmod{p-1}$, we get that $p \mid g = \gcd(a^n + b, b^n + a)$, so by FLT, $p \mid a + 1, p \mid b + 1 \implies p \mid 2\implies p=2$. If $ab+1=2$ then $\boxed{a=b=1}$ Otherwise $ab+1\equiv 0\pmod{4}\implies a,b\equiv \pm 1\pmod{4}$. WLOG $a \equiv -1 \pmod{4}$ and $b \equiv 1 \pmod{4}$. If $n$ is odd then we obtain that $a^n + b$ and $b^n + a$ are both divisible by $4$, and therefore $4 \mid g$. But having $n$ even we get $a^n + b \equiv 2 \pmod{4}$ and $4 \nmid a^n + b$, a contradiction, so we are done!

Note that $ab+1 \mid g \mid a-b$, so indeed we must have $a =b $, from where the only working pair is $(1, 1).

For all n, which are positive integers ($a=b=1$) is the only solution.