Maths Olympiad Prep

Library / /412 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

16. Does there exist 2011 different positive integers such that for any two numbers aa and bb, we have
ab=(a,b) |a-b|=(a, b)

holds?

Solution

16. Existence.
Below is the proof using mathematical induction.
(1) Since ab(a,b)|a-b| \geqslant (a, b), we have ab=(a,b)(ab)a|a-b| = (a, b) \Leftrightarrow (a-b) \mid a.
Clearly, 2 and 3 satisfy the condition.
(2) Assume there exist k(kN+)k\left(k \in \mathbf{N}_{+}\right) positive integers a1,a2a_{1}, a_{2},
,ak\cdots, a_{k}, such that for any 1i<jk1 \leqslant i < j \leqslant k, we have
aiajai \left|a_{i}-a_{j}\right| \mid a_{i} \text{. }

Then we can choose such k+1k+1 numbers:
b1=a1a2ak,b2=a1a2ak+a1,b3=a1a2ak+a2,bk+1=a1a2ak+ak. \begin{array}{l} b_{1}=a_{1} a_{2} \cdots a_{k}, \\ b_{2}=a_{1} a_{2} \cdots a_{k} + a_{1}, \\ b_{3}=a_{1} a_{2} \cdots a_{k} + a_{2}, \\ \cdots \cdots \cdot \\ b_{k+1}=a_{1} a_{2} \cdots a_{k} + a_{k} . \end{array}

For any 1i<jk+11 \leqslant i < j \leqslant k+1, we have
bibj=ai1aj1(a0=0) b_{i}-b_{j}=a_{i-1}-a_{j-1}\left(a_{0}=0\right) \text{. }

Since (ai1aj1)a1a2ak\left(a_{i-1}-a_{j-1}\right) \mid a_{1} a_{2} \cdots a_{k},
(ai1aj1)ai1 \left(a_{i-1}-a_{j-1}\right) \mid a_{i-1} \text{, }

it follows that (ai1aj1)bi\left(a_{i-1}-a_{j-1}\right) \mid b_{i}.
Thus, (bibj)bi\left(b_{i}-b_{j}\right) \mid b_{i}.
Therefore, there exist k+1k+1 numbers that satisfy the problem's requirements.
From (1) and (2), we can conclude that there exist any finite number of numbers that satisfy the requirement, and of course, 2011 numbers can also be found.

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.