Maths Olympiad Prep

Library / Mongolian Mathematical Olympiad Round 3 /2 of 12

Mongolian Mathematical Olympiad Round 3

Number theory Difficulty 5.4 AIME, harder Prove it Mongolia

Let aa and bb be integers with ∣a∣≥2|a| \ge 2. Prove that the sequence a1+b,a2+b,…,an+b,…a^1 + b, a^2 + b, \dots, a^n + b, \dots has 2022 consecutive members consisting of composite numbers.

Solution

It is clear if aa and bb are not relatively prime, thus we assume that aa and bb are relatively prime.
For n≥1n \ge 1, let an=an+ba_n = a^n + b. First we choose l≥0l \ge 0 such that ∣a∣l>∣b∣|a|^l > |b|. Then for any n≥l+1n \ge l+1, we have ∣an∣<∣a∣n+∣a∣l≤2∣a∣n−∣a∣l<∣an+1∣|a_n| < |a|^n + |a|^l \le 2|a|^n - |a|^l < |a_{n+1}|.
In particular, for any n≥l+3n \ge l+3, we have ∣an∣≥2|a_n| \ge 2. Let m=l+3m = l+3 and let N=2022N = 2022. Each of am+1,am+2,…,am+Na_{m+1}, a_{m+2}, \dots, a_{m+N} has at least one prime divisor, and we choose a prime divisor for each: p1∣am+1p_1 \mid a_{m+1}, p2∣am+2p_2 \mid a_{m+2}, …\dots, pN∣am+Np_N \mid a_{m+N}. Clearly (a,pi)=1(a, p_i) = 1 for each 1≤i≤N1 \le i \le N.
Now let k=(p1−1)(p2−1)…(pN−1)≥1k = (p_1-1)(p_2-1)\dots(p_N-1) \ge 1. Then am+k+i=am+i(ak−1)+am+ia_{m+k+i} = a^{m+i}(a^k-1) + a_{m+i} is divisible by pip_i by Fermat's theorem for any 1≤i≤N1 \le i \le N. Moreover, ∣am+k+i∣>∣am+i∣|a_{m+k+i}| > |a_{m+i}|. Hence am+k+1,am+k+2,…,am+k+Na_{m+k+1}, a_{m+k+2}, \dots, a_{m+k+N} are all composite.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.