Competition problem — Number theory

Number theory Difficulty 6.0 National olympiad Prove it Austria

Let $M$ be a set containing positive integers with the following three properties:
(1) $2018 \in M$ .
(2) If $m \in M$ , then all positive divisors of $m$ are also elements of $M$ .
(3) For all elements $k, m \in M$ with $1 < k < m$ , the number $km + 1$ is also an element of $M$ .

Prove that $M = \mathbb{Z}_{\ge 1}$ .

Solution

We first show that $1$ , $2$ , $3$ , $4$ , $5$ are elements of $M$ :
As divisors of $2018$ , the numbers $1$ , $2$ and $1009$ are elements of $M$ . Therefore, $2019 = 2 \cdot 1009 + 1$ and its divisor $3$ are elements of $M$ . We now obtain $7 = 2 \cdot 3 + 1$ and $15 = 2 \cdot 7 + 1$ and therefore the divisor $5$ of $15$ as elements of $M$ . Considering $16 = 3 \cdot 5 + 1$ , we see that $4 \in M$ .

We now show by induction that $\{1, 2, \dots, 2k-1\} \subseteq M$ for $k \ge 1$ .
This has been shown above for $k \le 3$ . Assume that the assertion holds for some $k \ge 3$ . Then we only have to verify that $2k$ and $2k+1$ are elements of $M$ , too.

It is clear that $2k+1 = 2 \cdot k + 1$ is an element of $M$ due to $k \ge 3$ . This implies that $(2k)^2 = (2k-1)(2k+1) + 1$ and its divisor $2k$ are elements of $M$ . This concludes the proof of the assertion and shows that $M$ consists of all positive integers.

Looking for a route rather than 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.