Maths Olympiad Prep

Library / /2 of 18

Number theory Difficulty 5.3 AIME, harder Prove it China

Given an integer k3k \ge 3 and a sequence {an}\{a_n\} that satisfies ak=2ka_k = 2k and for each n>kn > k,
an={an1+1,if an1 and n are coprime,2n,otherwise. a_n = \begin{cases} a_{n-1} + 1, & \text{if } a_{n-1} \text{ and } n \text{ are coprime,} \\ 2n, & \text{otherwise.} \end{cases}
Prove that anan1a_n - a_{n-1} is a prime for infinitely many nn. (Posed by Zhu Huawei)

Solution

Suppose that al=2la_l = 2l, lkl \ge k. Let pp be the least prime divisor of k1k-1. Then (l1,i)={1,1i<p,p,i=p,(l-1, i) = \begin{cases} 1, & 1 \le i < p, \\ p, & i = p, \end{cases} and thus
(2l+i2,l+i1)={1,1i<p,p,i=p. (2l + i - 2, l + i - 1) = \begin{cases} 1, & 1 \le i < p, \\ p, & i = p. \end{cases}
From (1) we know that
al+i1={2l+i1,1i<p,2l+2p2,i=p. a_{l+i-1} = \begin{cases} 2l + i - 1, & 1 \le i < p, \\ 2l + 2p - 2, & i = p. \end{cases}
Then al+p1al+p2=(2l+2p2)(2l+p2)=pa_{l+p-1} - a_{l+p-2} = (2l+2p-2) - (2l+p-2) = p is a prime number, al+p1=2(l+p1)a_{l+p-1} = 2(l+p-1). From the discussion above, we know that there are infinitely many lkl \ge k, such that al=2la_l = 2l and al+p1al+p2=pa_{l+p-1} - a_{l+p-2} = p is the least prime divisor of l1l-1.

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 and solution reproduced as published; topic and difficulty added by this site.