Track / Stage 6 / 184 of 400 #1184 of 1964

Problem 1184

National Olympiad, first round

Number theory Difficulty 6.2 Prove it

TN2. Let $S \subset\{1, \ldots, n\}$ be a nonempty set, where $n$ is a positive integer. We denote by $s$ the greatest common divisor of the elements of the set $S$ . We assume that $s \neq 1$ and let $d$ be its smallest divisor greater than 1 . Let $T \subset\{1, \ldots, n\}$ be a set such that $S \subset T$ and $|T| \geq 1+\left[\frac{n}{d}\right]$ . Prove that the greatest common divisor of the elements in $T$ is 1 .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution. Let $t$ be the greatest common divisor of the elements in $T$ . Due to the fact that $S \subset T$ , we immediately get that $t / s$ . Let us assume for the sake of contradiction that $t \neq 1$ . From the previous observation we get that $t \geq d$ .

By taking into account that $|T| \geq 1+\left[\frac{n}{d}\right]$ , we infer that we can find at least $1+\left[\frac{n}{d}\right]$ elements in $T$ . All of them will be divisible by $t$ , and the largest of them, which we shall denote by $M$ , will be at least $t \cdot\left(1+\left[\frac{n}{d}\right]\right)$ . On the other hand, $t \geq d$ , hence

$M \geq t \cdot\left(1+\left[\frac{n}{d}\right]\right) \geq d \cdot\left(1+\left[\frac{n}{d}\right]\right)>d \cdot \frac{n}{d}=n$

Therefore, $M>n$ , which contradicts the fact that $M \in\{1, \ldots, n\}$ . In conclusion, $t=1$ , as desired.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.