Каждое натуральное число в виде разности взаимопр. составных

[Ktina]

Докажите, что каждое натуральное число можно представить в виде разности двух взаимно простых составных чисел.
(Московский турнир математических боёв)

А чем плохо следующее представление?

$$n=((4n)!+2n+1)-((4n)!+n+1)$$

А если не плохо, то какое решение имел в виду автор?

[ИСН]

Всем хорошо. Возможно, лучше авторского. Но это задача такая простая, что тут как ни ходи - поставишь мат следующим ходом.
Например, думаем так. Рассмотрим все пары $(k,k+n)$ с $k$, пробегающим до чего-то большого. Вычеркнем все пары, где НОД не 1. Останется примерно $\varphi(n)$ из каждых $n$, то есть количество, растущее линейно. Вычеркнем все с простыми сверху или снизу. А ведь простых у нас асимптотически мало. Значит, даже если эти "сверху или снизу" никогда не совпадают, то после вычёркивания что-то останется.

[Ktina]

ИСН в сообщении #695595 писал(а):

Останется примерно $\varphi(n)$ из каждых $n$, ...

Это ж как-то доказывать надо...

-- 14.03.2013, 17:38 --

ИСН в сообщении #695595 писал(а):

А ведь простых у нас асимптотически мало.

И это тоже...

-- 14.03.2013, 17:46 --

ИСН в сообщении #695595 писал(а):

...как ни ходи - поставишь мат следующим ходом. ...

(Оффтоп)

Кстати, видела в каком-то учебнике именно такую позицию. Там у белых было очень много вариантов для следующего хода, и каждый из этих возможных ходов был матующим. Хоть убей, не помню эту позицию, запомнилась только её красота.