Find all sets $X$ consisting of at least two positive integers such that for every two elements $m,n\in X$, where $n>m$, there exists an element $k\in X$ such that $n=mk^2$.
Problem
Source: Baltic Way 2004 Problem 7
Tags: ratio, number theory proposed, number theory
25.10.2005 20:22
I will show that all such sets X are sets of the forms $\left\{a;\;a^3\right\}$, where a can be an arbitrary integer > 1. In fact, let X be a set consisting of at least two positive integers such that for every two elements m and n of the set X, where n > m, there exists an element k of X such that $n=mk^2$. In other words, we demand that for every two elements m and n of the set X, where n > m, the ratio $\frac{n}{m}$ is the square of an element of X. Write our set X in the form $\left\{a_1;\;a_2;\;...\right\}$, where $a_1 < a_2 < ...$. Hereby, the dots don't imply that the set X must be infinite; the set X can be finite as well. We don't know a priori how many elements X has, but we know that the set X has at least 2 elements, so that we can consider the smallest two elements $a_1$ and $a_2$ of X. First we show that 1 is not an element of X. In fact, if 1 were an element of x, it would be the smallest element of X; thus, we would have $a_1=1$, and since $a_2 > 1$, it would follow that $\frac{a_2}{1}$ is the square of an element of X; in other words, $a_2$ is the square of an element of X; but this latter element of X would be > 1 and $< a_2$ (this is because $a_2 > 1$), what contradicts the assumption that there is no element of X between $1=a_1$ and $a_2$ (in fact, remember that $a_1 < a_2 < ...$). Hence, 1 is not an element of X. Thus, all elements of X are > 1, i. e. we have $1 < a_1 < a_2 < ...$. Since $a_2 > a_1$, the ratio $\frac{a_2}{a_1}$ is the square of an element of X. But this latter element of X can only be $a_1$, since $\sqrt{\frac{a_2}{a_1}} \leq \frac{a_2}{a_1} < a_2$ (because of $1 < a_1$), and $a_1$ is the only element of the set X which is $< a_2$. Hence, $\frac{a_2}{a_1} = a_1^2$, and $a_2 = a_1^3$. If the set X has only 2 elements, then this already yields our family of solutions: $X = \left\{a;\;a^3\right\}$, where a is an arbitrary integer > 1. Now consider the case when the set X has at least 3 elements, i. e. there is an element $a_3$. Since $a_3 > a_1$, the ratio $\frac{a_3}{a_1}$ is the square of an element of X. But this latter element of X must be either $a_1$ or $a_2$, since $\sqrt{\frac{a_3}{a_1}} \leq \frac{a_3}{a_1} < a_3$ (this is because $1 < a_1$), and $a_1$ and $a_2$ are the only elements of the set X which are $< a_3$. In the case $\frac{a_3}{a_1}=a_1^2$, we get $a_3=a_1^3$, so that $a_3=a_2$, contradicting with $a_2 < a_3$. Hence, only the case $\frac{a_3}{a_1}=a_2^2$ remains possible; since $a_2=a_1^3$, we thus have $a_3=a_1a_2^2=a_1\left(a_1^3\right)^2=a_1^7$. But on the other hand, since $a_3 > a_2$, the ratio $\frac{a_3}{a_2}$ is the square of an element of X. But $\frac{a_3}{a_2} = \frac{a_1^7}{a_1^3} = a_1^4 = \left(a_1^2\right)^2$, and $a_1^2$ is not an element of X (in fact, if it would be an element of X, it would lie between $a_1$ and $a_3 = a_1^7$, so it would be equal to $a_2$, but $a_2 = a_1^3 \neq a_1^2$). So we get a contradiction, and hence, the set X cannot have more than 2 elements. And thus, the family of solutions we found above, $X = \left\{a;\;a^3\right\}$ for $a \in \left\{2;\;3;\;4;\;...\right\}$, yields all solutions. This is in fact Darij's solution, re-posted.