IMO 2024 Q2 #
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 \ge N$.
We consider the sequence modulo ab+1
; if the exponent is -1
modulo φ(ab+1)
, the terms
are zero modulo ab+1
, so ab+1
divides g
, and all sufficiently large terms, so all terms,
from which we conclude that a=b=1
.
theorem
Imo2024Q2.Condition.symm_large_n
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
⋯.large_n = h.large_n
theorem
Imo2024Q2.Condition.N_le_large_n
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
h.N ≤ h.large_n
theorem
Imo2024Q2.Condition.symm_large_n_0
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
⋯.large_n_0 = h.large_n_0
theorem
Imo2024Q2.Condition.N_le_large_n_0
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
h.N ≤ h.large_n_0
theorem
Imo2024Q2.Condition.ab_add_one_dvd_a_pow_large_n_add_b
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
theorem
Imo2024Q2.Condition.ab_add_one_dvd_b_pow_large_n_add_a
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
theorem
Imo2024Q2.Condition.ab_add_one_dvd_a_pow_large_n_0_add_b
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
theorem
Imo2024Q2.Condition.ab_add_one_dvd_b_add_one
{a : ℕ}
{b : ℕ}
(h : Imo2024Q2.Condition a b)
:
This is to be determined by the solver of the original problem.
Equations
- Imo2024Q2.solutionSet = {(1, 1)}