Республиканская олимпиада по математике, 2016 год, 10 класс

Дано натуральное $N$. Докажите, что все натуральные делители числа $N$ можно выписать в последовательность $d_1$, $\ldots$, $d_k$ так, чтобы для каждого $1\le i < k$ одно из чисел $d_i/d_{i+1}$ и $d_{i+1}/d_i$ было простым. ( Д. Елиусизов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Докажем утверждение индукцией по количеству простых делителей числа. Если число имеет только один простой делитель $p_1$, то есть оно вида $p_1^{k_1}$, то можно выписать последовательность $1$, $p_1$, $\ldots$, $p_1^{k_1}$.
Предположим утверждение верно для числа, которое имеет $n \geq 1$ простых делителей. Докажем для числа, имеющего $n+1$ простых делителей следующим образом. Пусть $N = p_{n+1}^l\cdot N'$ ($p_{n+1}$ это $n+1$-ый простой делитель), где $N'$ имеет $n$ простых делителей и $d_1$, $\ldots$, $d_m$ искомая последовательность для $N'$. Тогда для всех делителей числа $N$, новую последовательность можно построить так: $$d_1,\ \ldots, \ d_m; \quad pd_m, \ \ldots, \ pd_1; \quad p^2d_1, \ \ldots,\ p^2d_m; \ \ldots.$$ Легко видеть, что эта последовательность содержит все делители $N$ по одному разу и что она удовлетворяет требуемому условию.