IMO 2002 Q3

Find all pairs of positive integers $m,n ≥ 3$ for which there exist infinitely many positive integers $a$ such that $(a^m+a-1) / (a^n+a^2-1)$ is itself an integer.

Solution

It suffices to find $(m,n)$ pairs for which $a^n+a^2-1 ∣ a^m+a-1$, where both sides are viewed as polynomials in $a$. This automatically gives $m ≤ n$, so we have $$a^n+a^2-1 ∣ (a^m+a-1)(a+1) - (a^n+a^2-1) = a^m(a+1) - a^n.$$ Since $a^n$ is coprime to $a^n+a^2-1$ we have $a^n+a^2-1 ∣ a^{m-n}(a+1)-1$, so $m-n+1 ≥ n$.

Because $n ≥ 3$, there exists a real root $0 < r < 1$ of $a^n+a^2-1$, whence $r^{m-n+1}+r^{m-n}-1 = 0$. But we must also have $m-n ≤ 2$, for otherwise $$r^{m-n+1}+r^{m-n}-1 ≤ r^n+r^{m-n}-1 < r^n+r^2-1 = 0.$$ This eliminates all possibilities except $m = 5, n = 3$, which is easily seen to satisfy the original condition.

theorem Imo2002Q3.natDegree_numerpol {m : ℕ} (hm : 3 ≤ m) : (Polynomial.X ^ m + Polynomial.X - 1).natDegree = m

theorem Imo2002Q3.monic_numerpol {m : ℕ} (hm : 3 ≤ m) : (Polynomial.X ^ m + Polynomial.X - 1).Monic

theorem Imo2002Q3.natDegree_denompol {n : ℕ} (hn : 3 ≤ n) : (Polynomial.X ^ n + Polynomial.X ^ 2 - 1).natDegree = n

theorem Imo2002Q3.monic_denompol {n : ℕ} (hn : 3 ≤ n) : (Polynomial.X ^ n + Polynomial.X ^ 2 - 1).Monic

theorem Imo2002Q3.proof_body {m n : ℕ} (hm : 3 ≤ m) (hn : 3 ≤ n) (h : {a : ℤ | 0 < a ∧ a ^ n + a ^ 2 - 1 ∣ a ^ m + a - 1}.Infinite) : m = 5 ∧ n = 3

theorem Imo2002Q3.result {m n : ℕ} (hm : 3 ≤ m) (hn : 3 ≤ n) : {a : ℤ | 0 < a ∧ a ^ n + a ^ 2 - 1 ∣ a ^ m + a - 1}.Infinite ↔ m = 5 ∧ n = 3