A 99

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A 99

G H J

Reveal topic tags

Divisibility Theory

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10, UpvoteFarm

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#2 h Jul 22, 2007, 2:45 AM • 3 Y

Y by Adventure10, UpvoteFarm, Mango247

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a