IMO 2024 N4 (P2)

Find all pairs $(a, b)$ of positive integers such that there exists a positive integer $g$ for which $\gcd(a^n + b, b^n + a) = g$ for all sufficiently large $n$.

Answer

$(1, 1)$.

Solution

We follow the AoPS solution ♯9 by Tintarn in this thread. We make it even simpler by only substituting twice. That is, pick some $n₀ ≥ N$ such that $a^{n₀ + 1} ≡ b^{n₀ + 1} ≡ 1 \pmod{ab + 1}$, then plug $n = n₀$ and $n = n₀ + 1$ (typically one chooses $n₀ ≡ -1 \pmod{φ(ab + 1)}$). Note that all solutions that I am aware of so far considers $ab + 1$.

theorem IMOSL.IMO2024N4.self_coprime_mul_succ (a b : ℕ) : a.Coprime (a * b + 1)

a is coprime with ab + 1.

theorem IMOSL.IMO2024N4.pow_totient_mul_succ_mul_modeq_one (a b k : ℕ) : a ^ ((a * b + 1).totient * k) ≡ 1 [MOD a * b + 1]

a^{φ(ab + 1) k} ≡ 1 (mod ab + 1).

theorem IMOSL.IMO2024N4.mul_succ_dvd_pow_add_of_pow_succ_modeq_one {a b n : ℕ} (h : a ^ (n + 1) ≡ 1 [MOD a * b + 1]) : a * b + 1 ∣ a ^ n + b

If a^{n + 1} ≡ 1 (mod ab + 1) then ab + 1 ∣ a^n + b.

theorem IMOSL.IMO2024N4.eq_one_of_mul_succ_right_dvd_succ {a b : ℕ} (ha : 0 < a) (hb : 0 < b) (h : a * b + 1 ∣ b + 1) : a = 1

If ab + 1 ∣ b + 1, then a = 1.

theorem IMOSL.IMO2024N4.final_solution {a b : ℕ} (ha : 0 < a) (hb : 0 < b) : (∃ (g : ℕ) (N : ℕ), ∀ n ≥ N, (a ^ n + b).gcd (b ^ n + a) = g) ↔ a = 1 ∧ b = 1

Final solution