Let $n \ge 2$ be a positive integer, with divisors \[1=d_{1}< d_{2}< \cdots < d_{k}=n \;.\] Prove that \[d_{1}d_{2}+d_{2}d_{3}+\cdots+d_{k-1}d_{k}\] is always less than $n^{2}$, and determine when it divides $n^{2}$.
Problem
Source:
Tags: Divisibility Theory
Peter
22.07.2007 05:45
nicetry007 wrote: The sum $ \sum_{i=1}^{k-1}d_{i}d_{i+1}= d_{k}d_{k-1}+d_{k-1}d_{k-2}+\cdots+d_{2}d_{1}$ $ \leq n\cdot \frac{n}{2}+\frac{n}{2}\cdot \frac{n}{3}+\cdots+\frac{n}{k-1}\cdot \frac{n}{k}= n^{2}\left[ 1\cdot\frac{1}{2}+\frac{1}{2}\cdot \frac{1}{3}+\cdots+\frac{1}{k-1}\cdot \frac{1}{k}\right] = n^{2}\left[ 1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\cdots+\frac{1}{k-1}-\frac{1}{k}\right] = n^{2}\left(1-\frac{1}{k}\right) < n^{2}$. Suppose $ n$ is a prime. $ n = 1.p$, $ d_{1}=1$ and $ d_{2}= p$ and $ n^{2}= p^{2}$. The sum $ \sum_{i=1}^{k-1}d_{i}d_{i+1}= 1 \cdot p = p$ and $ p | p^{2}$. Hence, whenever $ n$ is a prime, the sum divides $ n^{2}$. Suppose $ n$ is composite. This implies $ k \geq 3$. We have $ d_{1}= 1$ and $ d_{2}= p$ where $ p$ is ther smallest prime that divides $ n$. The sum $ \sum_{i=1}^{k-1}d_{i}d_{i+1}> d_{k}d_{k-1}= n\cdot \frac{n}{p}= \frac{n^{2}}{p}$. This helps us make the following useful observation. $ 1 < \frac{n^{2}}{\sum_{i=1}^{k-1}d_{i}d_{i+1}}< \frac{n^{2}}{d_{k}d_{k-1}}= \frac{n^{2}}{\frac{n^{2}}{p}}= p$.[Note the first inequality follows from the first part of the problem.] If $ \frac{n^{2}}{\sum_{i=1}^{k-1}d_{i}d_{i+1}}$ is an integer, then it should lie between $ 1$ and $ p$. But $ p$ is the smallest prime that divides $ n$. Hence, the ratio $ \frac{n^{2}}{\sum_{i=1}^{k-1}d_{i}d_{i+1}}$ cannot be an integer. Hence, the sum $ \sum_{i=1}^{k-1}d_{i}d_{i+1}| n^{2}$ if and only if $ n$ is a prime.