Для положительного целого числа $n\geq 2$ с делителями $1=d_1<d_2<\cdots<d_k=n$, докажи это $d_1d_2+d_2d_3+\cdots+d_{k-1}d_k<n^2$

Question

IMO 2002 P4 Let $n\geq 2$ натуральное число с делителями $1=d_1<d_2<\cdots<d_k=n$. Докажи это$d_1d_2+d_2d_3+\cdots+d_{k-1}d_k$ всегда меньше чем $n^2$, и определить, когда он является делителем $n^2$

Я пытаюсь ответить на этот вопрос, но у меня закончились идеи, может ли кто-нибудь дать небольшой намек или предложение? Пожалуйста, не давая мне решения.

Я пытаюсь использовать тот факт, что продукт $d_i$*$d_{i+1}$ является делителем $n^2$ (и все они разные) и, возможно, попытайтесь использовать формулу для суммы делителей, чтобы увидеть, меньше ли эта конкретная сумма, чем $n^2$

Answer 1

Подсказка 1: насколько большой может $d_{k-1}$ быть как функция $n$? Что о$d_{k-2}$?

Подсказка 2: пусть $p$ быть наименьшим простым делителем $n$. Что ты можешь сказать о$d_{k-1}$ с точки зрения $n,p$? Какой самый большой (собственный) делитель$n^2$?

Answer 2

поскольку $d$ является делителем $n$ если и только если $n/d$ есть, у нас есть $$d_1d_2+d_2d_3+\cdots+d_{k-1}d_k=\left(\frac{n^2}{d_1d_2}+\frac{n^2}{d_2d_3}+\cdots+\frac{n^2}{d_{k-1}d_k}\right)\leq n^2\sum_{j=1}^{k-1}\left(\frac{1}{d_j}-\frac{1}{d_{j+1}}\right)<\frac{n^2}{d_1}=n^2$$ $$\tag*{$\ left [\ text {поскольку $\frac{1}{d_jd_{j+1}}\leq\left(\frac{d_{j+1}-d_j}{d_jd_{j+1}}\right)=\left(\frac{1}{d_j}-\frac{1}{d_{j+1}}\right)$}\верно]$}$$

Для второй части пусть $n$ быть составным и $p$ быть наименьшим простым делителем $n$. Тогда у нас есть$$d_1d_2+d_2d_3+\cdots+d_{k-1}d_k>d_{k-1}d_k=\frac{n^2}{p}$$ Сейчас если $N=d_1d_2+d_2d_3+\cdots+d_{k-1}d_k$ является делителем $n$ тогда мы должны иметь $\frac{n^2}{N}\mid n^2$. Но$p>\frac{n^2}{N}$ противоречие, поскольку $p$ является наименьшим простым делителем $n^2$. Так$N\mid n^2$ если и только если $n$ это простое число.