Maths Olympiad Prep

Library / /2 of 3

Number theory Difficulty 8.4 Shortlist Prove it Taiwan

Let a1<a2<a3<a_1 < a_2 < a_3 < \dots be positive integers such that ak+1a_{k+1} divides 2(a1+a2++ak)2(a_1 + a_2 + \dots + a_k) for every k1k \ge 1. Suppose that for infinitely many primes pp, there exists kk such that pp divides aka_k. Prove that for every positive integer nn, there exists kk such that nn divides aka_k.

Solution

For every k2k \ge 2 define the quotient bk=2(a1++ak1)/akb_k = 2(a_1+\cdots+a_{k-1})/a_k, which must be a positive integer. We first prove the following properties of the sequence (bk)(b_k):

Claim 1. We have bk+1bk+1b_{k+1} \le b_k + 1.

Proof. By subtracting bkak=2(a1++ak1)b_k a_k = 2(a_1 + \cdots + a_{k-1}) from bk+1ak+1=2(a1++ak)b_{k+1} a_{k+1} = 2(a_1 + \cdots + a_k), we find that bk+1ak+1=bkak+2akb_{k+1} a_{k+1} = b_k a_k + 2a_k. From ak<ak+1a_k < a_{k+1} it follows that bk+2>bk+1b_k + 2 > b_{k+1}.

Claim 2. The sequence (bk)(b_k) is unbounded.

Proof. We start by rewriting bk+1ak+1=(bk+2)akb_{k+1}a_{k+1} = (b_k + 2)a_k as
ak+1=akbk+2bk+1ak+1ak(bk+2). a_{k+1} = a_k \cdot \frac{b_k + 2}{b_{k+1}} \Rightarrow a_{k+1} \mid a_k(b_k + 2).
If the sequence (bk)(b_k) were bounded, say by some positive integer BB, then the prime factors of the terms of the sequence (ak)(a_k) could only be primes less than or equal to B+2B+2 or those dividing a1a_1 or a2a_2, which contradicts the property in the statement of the problem.

Consider now an arbitrary positive integer nn. We assume n>b2n > b_2, otherwise we replace nn by an arbitrary multiple of nn that is bigger than b2b_2. By Claim 2, there exists kk such that bk+1nb_{k+1} \ge n. Consider the smallest such kk. From Claim 1, it follows that we must have bk=n1b_k = n-1 and bk+1=nb_{k+1} = n (we assumed n>b2n > b_2 to ensure that k2k \ge 2). We now find that
ak+1=akbk+2bk+1=akn+1n. a_{k+1} = a_k \cdot \frac{b_k + 2}{b_{k+1}} = a_k \cdot \frac{n+1}{n}.
Because nn and n+1n+1 are coprime, this immediately implies that aka_k is divisible by nn.

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 translated into English from zh; metadata (topic, difficulty) added by this project.