Maths Olympiad Prep

Library / /230 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Example 14([13.3]) Proof: In the sequence 2n3(n=2,3,)2^{n}-3(n=2,3, \cdots), there must exist an infinite subsequence, in which any two numbers are coprime.

Solution

Prove (i) For any odd number aa, there must be a d2d \geqslant 2 such that a2d1a \mid 2^{d}-1, and aa and 2d32^{d}-3 are coprime (Chapter 1, §3, Example 5).
(ii) Based on (i), use induction to construct the sequence. Take a1=223a_{1}=2^{2}-3. If a1,,aka_{1}, \cdots, a_{k} have been chosen, then take
ak+1=2d(k+1)3a_{k+1}=2^{d(k+1)}-3, where d(k+1)d(k+1) satisfies a1ak2d(k+1)1a_{1} \cdots a_{k} \mid 2^{d(k+1)}-1. Thus, an infinite subsequence a1,,ak,a_{1}, \cdots, a_{k}, \cdots of the sequence 2n3(n=2,3,)2^{n}-3(n=2,3, \cdots) is inductively defined.
(iii) From a1akak+1+2a_{1} \cdots a_{k} \mid a_{k+1}+2 and the fact that aja_{j} are all odd, the desired conclusion follows (why).

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.