Задача 4. Восемьдесят чисел подряд

Чем мешают маленькие простые делители

Пусть $m$ делится на простое число $p$. Тогда на $p$ делятся и числа $m - p$ и $m + p$ — с ними у $m$ общий делитель $p$, значит, они не взаимно просты с $m$.

Возьмём любой набор из 80 чисел подряд, в котором есть $m$. Если в нём есть $m + p$, он уже не подходит. Если нет, то набор кончается раньше $m + p$: его последнее число не больше $m + p - 1$, а первое — не больше

При $p \le 40$ это число не больше $m - p$. Значит, набор начинается не позже $m - p$ и кончается не раньше $m$, поэтому содержит $m - p$ — и снова не подходит. (Число $m - p$ здесь натуральное: оно не меньше первого числа набора.)

Вывод: если у $m$ есть простой делитель, не больший $40$, то $m$ — не особое. Например, особым не бывает ни одно чётное число и ни одно число, кратное $3$, $5$, …, $37$.

Какие числа особые

Пусть теперь $m > 1$ и все простые делители $m$ не меньше $41$ (тогда $m \ge 41$). Возьмём набор из 80 чисел от $m - 39$ до $m + 40$ — все они натуральные.

Любое другое число $x$ этого набора отличается от $m$ не больше чем на $40$. Если бы у $x$ и $m$ был общий простой делитель $p$, то $p$ делил бы и разность $x - m$, а значит, $p \le |x - m| \le 40$. Но у $m$ таких делителей нет. Поэтому каждое $x$ взаимно просто с $m$, и $m$ — особое.

Ещё особое число $1$: оно взаимно просто с любым числом. Итак, особые числа — это $1$ и числа, у которых все простые делители не меньше $41$: простые $41$, $43$, $47$, … и, например, $41\cdot 41 = 1681$, $41\cdot 43 = 1763$, $43\cdot 43 = 1849$.

Оценка НОД

Пусть $x < y$ — особые числа, не большие $1900$, и $d = \text{НОД}(x, y)$. Запишем $y = d\cdot t$. Так как $y > x \ge d$, то $t \ge 2$.

Каждый простой делитель $t$ делит и $y$, а у особого $y$ все простые делители не меньше $41$. Значит, $t \ge 41$, и

Кроме того, $d$ делит особое число $x$, поэтому $d = 1$ или все простые делители $d$ не меньше $41$. Среди чисел от $1$ до $46$ такие только $1$, $41$ и $43$. Значит, $d \le 43$.

Пример с НОД 43

Возьмём $x = 43$ и $y = 1763 = 41\cdot 43$. Оба числа особые по шагу 2: у них простые делители $41$ и $43$. Можно и предъявить наборы: для $43$ — числа от $1$ до $80$, для $1763$ — от $1723$ до $1802$.

Их НОД равен $43$, и оба числа не больше $1900$. Значит, наибольший возможный НОД равен $43$.

Второй вариант

Рассуждение то же, меняются числа. Если $k$ делится на простое $p$ и $2p \le 50$, то есть $p \le 23$, то любой набор из 50 чисел подряд с числом $k$ содержит $k - p$ или $k + p$: набор без $k + p$ начинается не позже $k + p - 50 \le k - p$. Если же $k > 1$ и все простые делители $k$ не меньше $29$, подходит набор от $k - 24$ до $k + 25$ (при $k \ge 29$ все эти числа натуральные): каждое его число отличается от $k$ не больше чем на $25$, а общий простой делитель делил бы эту разность.

Ещё особое число $1$: оно взаимно просто с любым числом. Значит, особые числа — это $1$ и числа с простыми делителями не меньше $29$. Для особых $x < y \le 1000$ с $d = \text{НОД}(x, y)$ и $y = d\cdot t$ получаем $t \ge 29$, откуда $d \le \frac{1000}{29} < 35$. Среди чисел до $34$ простые делители не меньше $29$ только у $1$, $29$ и $31$, поэтому $d \le 31$.

Пример: $31$ и $899 = 29\cdot 31$ — оба особые (наборы от $1$ до $50$ и от $871$ до $920$), их НОД равен $31$. Следующий кандидат $37$ не проходит: $37\cdot 29 = 1073 > 1000$.