Maths Olympiad Prep

Library / /8 of 8

Number theory Difficulty 6.9 National Olympiad Prove it Romania

Consider the sequence of integers a0,a1,a2,a_0, a_1, a_2, \dots, where an=n62017a_n = n^6 - 2017 if nn is divisible by 77, and an=17(n62017)a_n = \frac{1}{7}(n^6 - 2017) otherwise. Determine the largest length a string of consecutive terms sharing a common divisor greater than 11 may have.

Solution

To show it less than 33, we let bn=n62017b_n = n^6 - 2017, n=0,1,2,n = 0, 1, 2, \dots, and prove that
gcd(bn1,bn,bn+1)={1if n0,±1(mod7),7if n±2,±3(mod7). \text{gcd}(b_{n-1}, b_n, b_{n+1}) = \begin{cases} 1 & \text{if } n \equiv 0, \pm 1 \pmod 7, \\ 7 & \text{if } n \equiv \pm 2, \pm 3 \pmod 7. \end{cases}
Fix an index nn, and let dd be a positive integer dividing bn1,bnb_{n-1}, b_n and bn+1b_{n+1}. Since at least one of bn1,bn,bn+1b_{n-1}, b_n, b_{n+1} is odd, so is dd. The numbers bn+12bn+bn1=2(15n4+15n2+1)b_{n+1}-2b_n+b_{n-1} = 2(15n^4+15n^2+1) and bn+1bn1=4n(3n4+10n2+3)b_{n+1}-b_{n-1} = 4n(3n^4+10n^2+3) are both divisible by dd. Since dd is odd, it divides 15n4+15n2+115n^4+15n^2+1, so dd is coprime to nn, hence it divides 3n4+10n2+33n^4+10n^2+3 as well. Write 7(5n2+2)=5(3n4+10n2+3)(15n4+15n2+1)7 \cdot (5n^2+2) = 5 \cdot (3n^4+10n^2+3) - (15n^4+15n^2+1) to infer that 7(5n2+2)7 \cdot (5n^2+2) is divisible by dd. Since 3(5n2+2)(5n2+3)=5(15n4+15n2+1)+133 \cdot (5n^2+2)(5n^2+3) = 5 \cdot (15n^4+15n^2+1)+13, it follows that dd is one of 1,7,13,7131, 7, 13, 7 \cdot 13. To conclude the proof, notice that no bkb_k is divisible by 1313.

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.