Competition problem — Number theory

Library / /2 of 57

Number theory Difficulty 5.2 AIME, harder Prove it Russia

Let positive integers $d$ and $d'$ ( $d' > d$ ) be two divisors of positive integer $n$ . Prove that $d' > d + \frac{d^2}{n}$ .

Натуральные числа $d$ и $d'$ , $d' > d$ -- делители натурального числа $n$ . Докажите, что $d' > d + \frac{d^2}{n}$ .

Solution

Поскольку числа $f = n/d$ и $f' = n/d'$ целые, а $f > f'$ , имеем $f - f' \ge 1$ , или
$1 \le \frac{n}{d} - \frac{n}{d'} = \frac{(d' - d)n}{dd'} < \frac{(d' - d)n}{d^2}.$
Домножая на $\frac{d^2}{n}$ , получаем $d' - d > \frac{d^2}{n}$ , что и требовалось доказать.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.