Track / Stage 4 / 31 of 340 #291 of 2000

Problem 291

AMC 12 late, AIME early

Number theory Difficulty 4.6 Prove it 2007 Shortlist JBMO · JBMO · 2007

Problem:

Let $A$ be a set of positive integers containing the number $1$ and at least one more element. Given that for any two different elements $m, n$ of $A$ the number $\frac{m+1}{(m+1, n+1)}$ is also an element of $A$ , prove that $A$ coincides with the set of positive integers.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Solution:

Let $a > 1$ be the lowest number in $A \setminus \{1\}$ . For $m = a$ , $n = 1$ one gets $y = \frac{a+1}{(2, a+1)} \in A$ . Since $(2, a+1)$ is either $1$ or $2$ , then $y = a+1$ or $y = \frac{a+1}{2}$ .

But $1 < \frac{a+1}{2} < a$ , hence $y = a+1$ . Applying the given property for $m = a+1$ , $n = a$ one has $\frac{a+2}{(a+2, a+1)} = a+2 \in A$ , and inductively $t \in A$ for all integers $t \geq a$ .

Furthermore, take $m = 2a-1$ , $n = 3a-1$ (now in $A$ !); as $(m+1, n+1) = (2a, 3a) = a$ one obtains $\frac{2a}{a} = 2 \in A$ , so $a = 2$ , by the definition of $a$ .

The conclusion follows immediately.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.