Maths Olympiad Prep

Library / /5 of 61

Number theory Difficulty 5.7 AIME, harder Prove it Canada

Problem:

Call a positive integer nn practical if every positive integer less than or equal to nn can be written as the sum of distinct divisors of nn.

For example, the divisors of 66 are {1,2}\{1, 2\}, {3}\{3\}, and {6}\{6\}. Since
1={1},2={2},3={3},4={1}+{3},5={2}+{3},6={6}, 1=\{1\}, \quad 2=\{2\}, \quad 3=\{3\}, \quad 4=\{1\}+\{3\}, \quad 5=\{2\}+\{3\}, \quad 6=\{6\},
we see that 66 is practical.

Prove that the product of two practical numbers is also practical.

Solution

Solution:

Let pp and qq be practical. For any kpqk \leq p q, we can write
k=aq+b with 0ap, 0b<q. k = a q + b \text{ with } 0 \leq a \leq p,\ 0 \leq b < q.
Since pp and qq are practical, we can write
a=c1++cm,b=d1++dn a = c_1 + \ldots + c_m, \quad b = d_1 + \ldots + d_n
where the cic_i's are distinct divisors of pp and the djd_j's are distinct divisors of qq. Now
k=(c1++cm)q+(d1++dn)=c1q++cmq+d1++dn. \begin{aligned} k &= (c_1 + \ldots + c_m) q + (d_1 + \ldots + d_n) \\ &= c_1 q + \ldots + c_m q + d_1 + \ldots + d_n. \end{aligned}
Each of ciqc_i q and djd_j divides pqp q. Since dj<qciqd_j < q \leq c_i q for any i,ji, j, the ciqc_i q's and djd_j's are all distinct, and we conclude that pqp q is practical.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.