Задача 6. Простые частные, составные остатки

Что требуется от каждого делителя

Пусть такое $n$ нашлось. Для каждого делителя $k$ от $10$ до $1000$ запишем деление с остатком:

Здесь $q_k$ — неполное частное, $r_k$ — остаток. По условию все $q_k$ — различные нечётные простые числа, а все $r_k$ — составные. Составное число — это число, у которого есть делитель, отличный от $1$ и от него самого: $4, 6, 8, 9, 10, \ldots$ Поэтому $r_k\ge 4$: остатки $0$, $1$, $2$, $3$ и вообще простые остатки запрещены.

Разбирать все $991$ делитель сразу не нужно. Посмотрим только на делители от $10$ до $20$ — их одиннадцать. При делении на число, не большее $20$, остаток меньше $20$. А составных чисел, меньших $20$, ровно десять:

Значит, каждый из одиннадцати остатков $r_{10}, r_{11}, \ldots, r_{20}$ — одно из этих десяти чисел.

Зачем это нужно: условие «остатки составные» выглядит слабым, но на маленьких делителях оно оставляет остаткам очень мало места — и это можно посчитать.

Одиннадцать делителей, десять коробок

Представим десять коробок с надписями $4, 6, 8, 9, 10, 12, 14, 15, 16, 18$ и одиннадцать карточек — делители $10, 11, \ldots, 20$. Карточку с делителем $k$ кладём в коробку с надписью $r_k$. Карточек одиннадцать, коробок десять, поэтому в какой-то коробке окажутся две карточки (рисунок ниже). Это принцип Дирихле: если предметов больше, чем ящиков, в каком-то ящике лежат хотя бы два.

Итак, найдутся два делителя $a<b$ (оба от $10$ до $20$), у которых остатки одинаковы: $r_a=r_b$. Обозначим этот общий остаток через $r$, а частные — через $p=q_a$ и $q=q_b$. Это различные нечётные простые числа.

Как до этого догадаться: когда остатков «мало», а делителей «много», первая мысль — поискать совпадение. Совпадение остатков — редкая удача в задачах про деление: оно даёт точное равенство, а не только неравенство.

Одинаковый остаток даёт $ap=bq$

Запишем $n$ двумя способами:

Вычтем $r$ из обеих записей: $n-r=ap=bq$ (рисунок ниже). Число $n-r$ разложено на множители двумя способами.

Посмотрим на произведение $ap$. Оно равно $bq$, значит, делится на простое число $q$. Разложим $a$ на простые множители; тогда разложение числа $ap$ состоит из простых множителей числа $a$ и ещё одного множителя $p$. Простое число $q$ должно быть среди них. Но $q\ne p$ — частные различны, — так что $q$ встречается среди простых множителей числа $a$. Значит, $q$ делит $a$. Точно так же из $bq=ap$ получаем, что $p$ делит $b$.

Но $a$ и $b$ — числа от $10$ до $20$. Делитель числа не больше самого числа, поэтому

Оба частных — маленькие простые числа, не больше $20$.

Почему это главный шаг: условие про простые частные до сих пор не работало. Именно равенство $ap=bq$ вместе с простотой $p$ и $q$ запирает оба частных в пределах $20$.

Такое $n$ слишком мало для делителя $1000$

Теперь оценим $n$. У нас $n=ap+r$, где $a<b\le 20$, так что $a\le 19$; частное $p$ — простое число, не большее $20$, значит $p\le 19$; остаток $r$ — составное число, меньшее $20$, значит $r\le 18$. Получаем

Но тогда $n<1000$, и при делении $n$ на $1000$ неполное частное равно $0$: $n=1000\cdot 0+n$. Нуль — не простое число (тем более не нечётное простое). Это противоречит условию для делителя $1000$.

Значит, предположение неверно: такого натурального $n$ не существует.

Проверим, что ничего не пропущено. Мы использовали: остатки при делении на $10,\ldots,20$ составные (шаги 1–2), частные $p$ и $q$ — различные простые (шаг 3), частное при делении на $1000$ — простое (шаг 4). Все три факта взяты прямо из условия, а $1000$ входит в диапазон делителей. Случай $n<10$ отдельно разбирать не нужно: для него вывод тот же — частное при делении на $1000$ равно $0$.