Competition problem — Number theory

Library / /47 of 48

Number theory Difficulty 8.0 Shortlist Prove it Asia Pacific Mathematics Olympiad (APMO)

Determine all finite nonempty sets $S$ of positive integers satisfying
$\frac{i+j}{(i, j)} \quad \text{is an element of } S \text{ for all } i, j \text{ in } S,$
where $(i, j)$ is the greatest common divisor of $i$ and $j$ .

Solution

Let $k \in S$ . Then $\frac{k+k}{(k, k)}=2$ is in $S$ as well.

Suppose for the sake of contradiction that there is an odd number in $S$ , and let $k$ be the largest such odd number. Since $(k, 2)=1$ , $\frac{k+2}{(k, 2)}=k+2>k$ is in $S$ as well, a contradiction. Hence $S$ has no odd numbers.

Now suppose that $\ell>2$ is the second smallest number in $S$ . Then $\ell$ is even and $\frac{\ell+2}{(\ell, 2)}=\frac{\ell}{2}+1$ is in $S$ . Since $\ell>2 \Longrightarrow \frac{\ell}{2}+1>2$ , $\frac{\ell}{2}+1 \geq \ell \Longleftrightarrow \ell \leq 2$ , a contradiction again.

Therefore $S$ can only contain $2$ , and $S=\{2\}$ is the only solution.

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.