gcd (a^n+b,b^n+a) is constant

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EthanWYX2009

827 posts

EthanWYX2009

#1 h Jul 16, 2024, 1:17 PM • 16 Y

Y by MathIQ., aaaa_27, NO_SQUARES, GeoKing, VIATON, aidan0626, kamatadu, Sedro, Rounak_iitr, sevket12, Eka01, eduD_looC, farhad.fritl, MS_asdfgzxcvb, cubres, Ibrahim_K

Determine all pairs $(a,b)$ of positive integers for which there exist positive integers $g$ and $N$ such that
$\gcd (a^n+b,b^n+a)=g$ holds for all integers $n\geqslant N.$ (Note that $\gcd(x, y)$ denotes the greatest common divisor of integers $x$ and $y.$ )

Proposed by Valentio Iverson, Indonesia

This post has been edited 5 times. Last edited by EthanWYX2009, Jul 19, 2024, 5:26 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hotmonkey1

2193 posts

hotmonkey1

#2 h Jul 16, 2024, 1:19 PM • 1 Y

Y by cubres

spoilered question

This post has been edited 1 time. Last edited by hotmonkey1, Jul 16, 2024, 1:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IndoMathXdZ

691 posts

IndoMathXdZ

#3 h Jul 16, 2024, 1:22 PM • 88 Y

Y by ATGY, hotmonkey1, CT17, ChubbyTomato426, lucas3617, aaaa_27, Assassino9931, kingu, CyclicISLscelesTrapezoid, Aryan-23, Sylvestra, BlazingMuddy, InternetPerson10, math90, Davi Medeiros, GuvercinciHoca, Quidditch, Jalil_Huseynov, bin_sherlo, Supertinito, math_comb01, navi_09220114, Funcshun840, Stuffybear, nmoon_nya, ehuseyinyigit, GeoMetrix, Seicchi28, trk08, hamon, thdnder, GeoKing, Mathological03, Sedro, eg4334, Mogmog8, lpieleanu, szpolska, ihatemath123, GorgonMathDota, aidan0626, EpicBird08, NO_SQUARES, talkon, timon92, OronSH, khina, justJen, mathfan2020, MathisWow, centslordm, megarnie, tricky.math.spider.gold.1, ohiorizzler1434, iamnotgentle, MS_Kekas, crocodilepradita, gghx, kamatadu, Filipjack, Capryon, pepat, avisioner, bachkieu, Supercali, MathIQ., RobertRogo, WinterSecret, TheMathCruncher_007, RevolveWithMe101, sarjinius, eduD_looC, erringbubble, MAKEANALITGREATAGAIN2018, khan.academy, Kingsbane2139, oVlad, MathPassionForever, Nartku, Kosiu, somebodyyouusedtoknow, farhad.fritl, GreenTea2593, DensSv, MS_asdfgzxcvb, cubres, giangtruong13, DroneChaudhary

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.

Remark about problem difficulty (spoilers)
Remark about problem creation

This post has been edited 3 times. Last edited by IndoMathXdZ, Jul 16, 2024, 6:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Physicsknight

635 posts

Physicsknight

#4 h Jul 16, 2024, 1:27 PM • 2 Y

Y by ehuseyinyigit, cubres

$\text{Very nice problem Valentino}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathhotspot

70 posts

mathhotspot

#6 h Jul 16, 2024, 1:47 PM • 2 Y

Y by ehuseyinyigit, cubres

Good advanced diophantine practice!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

thdnder

194 posts

thdnder

#7 h Jul 16, 2024, 1:48 PM • 9 Y

Y by BlazingMuddy, Funcshun840, Iveela, crocodilepradita, kamatadu, AlexCenteno2007, MathIQ., Bazo1, cubres

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$

This post has been edited 2 times. Last edited by thdnder, Jul 16, 2024, 2:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bsf714

61 posts

bsf714

#8 h Jul 16, 2024, 2:21 PM • 4 Y

Y by JanHaj, VicKmath7, Haris1, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tintarn

9027 posts

Tintarn

#9 h Jul 16, 2024, 2:27 PM • 20 Y

Y by thdnder, BlazingMuddy, CBMaster, Assassino9931, KST2003, Sedro, Fardad, CahitArf, crocodilepradita, pingupignu, adityaguharoy, sami1618, mastermind.hk16, Begli_I., tag-, Pratik12, MS_asdfgzxcvb, cubres, IndoMathXdZ, X.Luser

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.

This post has been edited 2 times. Last edited by Tintarn, Jul 23, 2024, 1:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BlazingMuddy

281 posts

BlazingMuddy

#10 h Jul 16, 2024, 2:40 PM • 5 Y

Y by abdirasulov, Nartku, ngduchieu1903, Pratik12, cubres

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!

This post has been edited 1 time. Last edited by BlazingMuddy, Jul 16, 2024, 3:09 PM
Reason: Add backstory

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_comb01

659 posts

math_comb01

#11 h Jul 16, 2024, 2:44 PM • 1 Y

Y by cubres

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

This post has been edited 1 time. Last edited by math_comb01, Jul 16, 2024, 2:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Funcshun840

17 posts

Funcshun840

#12 h Jul 16, 2024, 2:46 PM • 1 Y

Y by cubres

What is the MOHS of this problem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vsamc

3783 posts

vsamc

#13 h Jul 16, 2024, 3:09 PM • 4 Y

Y by centslordm, KevinYang2.71, persamaankuadrat, cubres

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EeEeRUT

50 posts

EeEeRUT

#14 h Jul 16, 2024, 3:15 PM • 1 Y

Y by cubres

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)$

This post has been edited 1 time. Last edited by EeEeRUT, Jul 16, 2024, 3:16 PM
Reason: Bracket

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shanelin-sigma

145 posts

shanelin-sigma

#15 h Jul 16, 2024, 3:30 PM • 2 Y

Y by Funcshun840, cubres

my solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1197 posts

Assassino9931

#16 h Jul 16, 2024, 3:36 PM • 6 Y

Y by GeoKing, Orestis_Lignos, Maths_Girl, AlexCenteno2007, EvansGressfield, cubres

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).

This post has been edited 6 times. Last edited by Assassino9931, Jul 16, 2024, 3:56 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonesPenguin

123 posts

SomeonesPenguin

#72 h Aug 4, 2024, 12:22 PM • 2 Y

Y by zzSpartan, cubres

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VicKmath7

1385 posts

VicKmath7

#73 h Aug 4, 2024, 2:50 PM • 8 Y

Y by GeoKing, iamnotgentle, Assassino9931, AlexCenteno2007, oolite, ehuseyinyigit, X.Allaberdiyev, cubres

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).

Solution

This post has been edited 6 times. Last edited by VicKmath7, Aug 4, 2024, 7:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math90

1474 posts

math90

#74 h Aug 21, 2024, 8:14 AM • 1 Y

Y by cubres

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)$ .

This post has been edited 1 time. Last edited by math90, Aug 21, 2024, 8:19 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1197 posts

Assassino9931

#75 h Sep 11, 2024, 4:50 PM • 1 Y

Y by cubres

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.)

This post has been edited 3 times. Last edited by Assassino9931, Sep 11, 2024, 5:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

straight

406 posts

straight

#76 h Sep 11, 2024, 5:20 PM • 1 Y

Y by cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1197 posts

Assassino9931

#77 h Sep 11, 2024, 5:25 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cali.Math

128 posts

Cali.Math

#78 h Sep 13, 2024, 7:54 PM • 1 Y

Y by cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1197 posts

Assassino9931

#79 h Sep 13, 2024, 7:54 PM • 3 Y

Y by pavel kozlov, VicKmath7, cubres

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.

This post has been edited 3 times. Last edited by Assassino9931, Sep 18, 2024, 8:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L13832

249 posts

L13832

#80 h Oct 3, 2024, 2:51 AM • 2 Y

Y by radian_51, cubres

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
$a^n+b\equiv a^{-1}+b\equiv \frac{ab+1}{a}\equiv 0\pmod{ab+1}$ $b^n+1\equiv a+b^{-1}\equiv \frac{ab+1}{b}\equiv 0\pmod{ab+1}$ Motivation
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! :yoda:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Golden_Verse

5 posts

Golden_Verse

#81 h Oct 31, 2024, 6:14 PM • 1 Y

Y by cubres

Answer
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Vedoral

89 posts

Vedoral

#82 h Dec 3, 2024, 11:51 PM • 1 Y

Y by cubres

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

927 posts

AshAuktober

#83 h Dec 8, 2024, 12:09 PM • 1 Y

Y by cubres

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).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zaidova

83 posts

zaidova

#84 h Jan 3, 2025, 7:40 PM • 1 Y

Y by cubres

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

This post has been edited 3 times. Last edited by zaidova, Jan 3, 2025, 7:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

549 posts

cursed_tangent1434

#85 h Feb 11, 2025, 11:09 AM • 1 Y

Y by ihategeo_1969

I just can't believe I didn't manage to solve this problem in contest. The idea of considering $ab+1$ is not that random either, especially since it is almost natural to consider $a+b$ at which point you decide that the considered expression had better be symmetric but also relatively prime to both $a$ and $b$ , which leads to the considered form.

The entirety of the problem is the following key claim.

Claim : For any such pair $(a,b)$ we must have $ab+1$ a power of two.

Proof : Consider a prime $p\mid ab+1$ . Then, since $\gcd(ab+1,a)=\gcd(ab+1,b)=1$ it follows that $p\nmid a,b$ and so letting $n=k(p-1)-1$ for sufficiently large positive integers $k$ we have,
$a^n+b \equiv \frac{1}{a}+b \equiv \frac{ab+1}{a} \equiv 0 \pmod{p}$ and
$a+b^n \equiv a+\frac{1}{b} \equiv \frac{ab+1}{b} \equiv 0 \pmod{p}$ which implies that $p \mid \gcd(a^n+b,b^n+a)$ . But then, if the $\gcd$ is eventually constant, we have that $p \mid \gcd(a^n+b,b^n+a)$ for all sufficiently large positive integers $n$ . But then, considering $n=k(p-1)$ for sufficiently large positive integers $k$ we have that,
$0 \equiv a^n+b \equiv b+1 \pmod{p}$ And similarly, $a+1 \equiv 0 \pmod{p}$ . But then, since $p\mid ab+1$ and $p \mid a+1$ it follows that $p \mid b-1$ which in conjunction with $p\mid b+2$ implies that $p=2$ . This means that there cannot exist any odd prime $p$ dividing $ab+1$ proving the claim.

Now, if $ab+1>2$ and
$ab+1=2^r$ for some $r \ge 2$ , it follows that $ab \equiv 3 \pmod{4}$ . Thus, $a\equiv 1 \pmod{4}$ and $b \equiv 3 \pmod{4}$ (or vice versa). But note that this means for even $n$ ,
$a^n + b \equiv 1+3 \equiv 0 \pmod{4}$ but
$a+b^n \equiv 1+1 \equiv 2 \pmod{4}$ Thus, $\nu_2(\gcd(a^n+b,b^n+a))=1$ . But note that for odd $n$ we have,
$a^n+b \equiv 1 + 3 \equiv 0 \pmod{4}$ and
$a+b^n \equiv 1 + 3 \equiv 0 \pmod{4}$ which implies that $4\mid \gcd(a^n+b,b^n+a)$ . But, if the $\gcd$ is eventually constant this is a clear contradiction, which implies that we must have $ab+1=2$ and thus, $a=b=1$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quantam13

96 posts

quantam13

#86 h Feb 25, 2025, 8:06 AM

Y by

Cute solution. The main idea is to consider the sequence modulo $ab+1$ , which can be motivated by " $n=-1$ ".

Z K Y