Обычное свойство натуральных чисел

[rightways]

Докажите , что любое натуральное число $n>23$ можно представить в виде суммы двух натуральных чисел $a$ и $b$ ($n=a+b$) с таким свойством: если $ab$ делится на некоторое простое $p$ то $\sqrt{n} \ge p$.

[Sonic86]

(Оффтоп)

При $n\geqslant 25$ гипотезу можно усилить: добавить ограничение $a\leqslant\sqrt{n}$. Проверил для $n\leqslant 10^5$.
Как доказывать, пока понятия не имею.
Для $n=k^2$ искомое разложение $k^2=k+k(k-1)$

[rightways]

А что означает $a \le \sqrt{n}$?

А насчет простого $p$, то эта задача из регионалки Ирана.

[Sonic86]

(Оффтоп)

rightways в сообщении #1013241 писал(а):

А что означает $a \le \sqrt{n}$?

Гипотеза: любое натуральное число $n\geqslant 25$ можно представить в виде суммы двух натуральных чисел $a\leqslant\sqrt{n}$ и $b$ ($n=a+b$) с таким свойством: если $ab$ делится на некоторое простое $p$ то $\sqrt{n} \geqslant p$.

rightways в сообщении #1013241 писал(а):

А насчет простого $p$, то эта задача из регионалки Ирана.

Наверное я просто не владею какой-то техникой.

[worm2]

Пусть $n$ находится между двумя квадратами соседних простых чисел: $q^2\leqslant n < p^2$, причём $q\geqslant 5$ ($n=24=16+8$ рассмотрим отдельно).
От нас требуется представить $n$ в виде суммы $a+b$, где в разложении $a$ и $b$ на простые сомножители отсутствуют простые, большие $q$ (или, что то же, не меньшие $p$, т.к. $p$ — следующее за $q$ простое).

Если $n<p(p-1)$, то разделим $n$ на $p-1$ с остатком. В этом случае и делитель, и неполное частное, и остаток будут меньше $p$, что даст нам сумму $n=k(p-1)+m$ с требуемыми свойствами. Если $n=p(p-1)$, то разложение аналогично: $n=(p-1)^2+(p-1)$.

Остаются $n$ в диапазоне от $p(p-1)+1$ до $p^2-1$. Для большинства из таких $n$ используем сумму $(p+1)(p-2)+m$ (тут, конечно, мы используем то, что $p+1$ составное, в разложении которого все простые меньше $p$). Она хороша для всех $m<p$, т.е. $n\leqslant p^2-3$. Осталось представить всего 2 числа: $p^2-1$ и $p^2-2$. Для первого возьмём сумму $(p-1)^2+2(p-1)$. А вот со вторым больше всего возни. Недаром почти все числа, непредставимые требуемой в задаче суммой ($n=23$ и $n=7$) имеют именно такой вид.

Используем представление $p^2-2=(p+3)(p-3)+7$. Оно годится, если $q\geqslant 7$. Остался единственный нерассмотренный случай $q=5$, $p=7$, $n=47$, который за вредность уничтожим сразу из всех возможных орудий: $2+45$, $32+15$ и $20+27$.