Maths Olympiad Prep

Library / /2 of 12

Number theory Difficulty 5.4 AIME, harder Prove it Mongolia

Let aa and bb be integers with a2|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 n1n \ge 1, let an=an+ba_n = a^n + b. First we choose l0l \ge 0 such that al>b|a|^l > |b|. Then for any nl+1n \ge l+1, we have an<an+al2anal<an+1|a_n| < |a|^n + |a|^l \le 2|a|^n - |a|^l < |a_{n+1}|.
In particular, for any nl+3n \ge l+3, we have an2|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: p1am+1p_1 \mid a_{m+1}, p2am+2p_2 \mid a_{m+2}, \dots, pNam+Np_N \mid a_{m+N}. Clearly (a,pi)=1(a, p_i) = 1 for each 1iN1 \le i \le N.
Now let k=(p11)(p21)(pN1)1k = (p_1-1)(p_2-1)\dots(p_N-1) \ge 1. Then am+k+i=am+i(ak1)+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 1iN1 \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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