Maths Olympiad Prep

Library / /473 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Prove it

Example 7([43.4]) Let nn be a positive integer greater than 1, and let its all positive divisors be d1,d2,,dkd_{1}, d_{2}, \cdots, d_{k}, satisfying 1=d1<d2<<dk=n1=d_{1}<d_{2}<\cdots<d_{k}=n. Let D=d1d2+d2d3++dk1dkD=d_{1} d_{2}+d_{2} d_{3}+\cdots+d_{k-1} d_{k}.
(i) Prove: D<n2D<n^{2};
(ii) Determine all nn such that DD divides n2n^{2}.

Solution

Using the knowledge from sections §1\S 1 and §2\S 2 of Chapter 1, we can prove (i). The proof of (i) relies on the fundamental properties of the divisors of a positive integer nn: If d1,d2,,dkd_{1}, d_{2}, \cdots, d_{k} are all the (positive) divisors of nn, then n/d1,n/d2,,n/dkn / d_{1}, n / d_{2}, \cdots, n / d_{k} are also all the (positive) divisors of nn, and when 1=d1<d2<<dk=n1=d_{1}<d_{2}<\cdots<d_{k}=n, we have dj=n/dkj+1d_{j}=n / d_{k-j+1} (see Theorem 2 in section §2\S 2 of Chapter 1). Using this property and the given conditions, we get
n2/d2=n2/(d1d2)D=d1d2+d2d3++dk1dk=n2{1/(dk1dk)+1/(dk2dk1)++1/(d1d2)}n2{(1/dk11/dk)+(1/dk21/dk1)++(1/d11/d2)}=n2(1/d11/dk)=n2(11/n)=n2n.\begin{aligned} n^{2} / d_{2}= & n^{2} /\left(d_{1} d_{2}\right) \leqslant D=d_{1} d_{2}+d_{2} d_{3}+\cdots+d_{k-1} d_{k} \\ = & n^{2}\left\{1 /\left(d_{k-1} d_{k}\right)+1 /\left(d_{k-2} d_{k-1}\right)+\cdots+1 /\left(d_{1} d_{2}\right)\right\} \\ \leqslant & n^{2}\left\{\left(1 / d_{k-1}-1 / d_{k}\right)+\left(1 / d_{k-2}-1 / d_{k-1}\right)\right. \\ & \left.+\cdots+\left(1 / d_{1}-1 / d_{2}\right)\right\} \\ = & n^{2}\left(1 / d_{1}-1 / d_{k}\right)=n^{2}(1-1 / n)=n^{2}-n . \end{aligned}

This proves (i). The leftmost inequality in the above expression holds with equality if and only if k=2k=2, i.e., the only positive divisors of nn are 1 and nn itself, which means nn is a prime number (see Definition 2 in section 2.2 of Chapter 1). Additionally, the rightmost inequality holds with equality if and only if n=2n=2 (why).

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.