Maths Olympiad Prep

Library / Belarusian Mathematical Olympiad /122 of 208

Belarusian Mathematical Olympiad

Number theory Difficulty 6.1 National Olympiad Prove it Belarus

For a positive integer nn write down all its positive integer divisors in increasing order: 1=d1<d2<⋯<dk=n1 = d_1 < d_2 < \dots < d_k = n.
Find all positive integers nn divisible by 20192019 such that n=d19⋅d20n = d_{19} \cdot d_{20}.

Solution

Answer: n=3⋅67318n = 3 \cdot 673^{18}; n=318⋅673n = 3^{18} \cdot 673.

Note that the equality n=d19⋅d20n = d_{19} \cdot d_{20} implies that nn has exactly 3838 divisors. Indeed,
n=d19⋅d20=d18⋅d21=d17⋅d22=⋯=d1⋅d38=d38. n = d_{19} \cdot d_{20} = d_{18} \cdot d_{21} = d_{17} \cdot d_{22} = \dots = d_1 \cdot d_{38} = d_{38}.
Hence either n=pαn = p^\alpha, where pp is prime and then α+1=38\alpha + 1 = 38, so n=p37n = p^{37}, or n=pα⋅qβn = p^\alpha \cdot q^\beta (pp and qq are different primes) and then 38=(α+1)(β+1)38 = (\alpha + 1)(\beta + 1), i.e. (α;β)=(1;18)(\alpha; \beta) = (1; 18) or (α;β)=(18;1)(\alpha; \beta) = (18; 1), so n=p⋅q18n = p \cdot q^{18} or n=p18⋅qn = p^{18} \cdot q, respectively.

Recall that nn is divisible by 20192019 while 2019=3⋅6732019 = 3 \cdot 673, where 33 and 673673 are primes. Therefore, n=3⋅67318n = 3 \cdot 673^{18} or n=673⋅318n = 673 \cdot 3^{18}. It remains to verify that in both of these cases n=d19⋅d20n = d_{19} \cdot d_{20}.

1. Let n=3⋅67318n = 3 \cdot 673^{18}. Arrange the divisors in an ascending order:
1<3<673<673⋅3<6732<6732⋅3<⋯<6739<6739⋅3<… 1 < 3 < 673 < 673 \cdot 3 < 673^2 < 673^2 \cdot 3 < \dots < 673^9 < 673^9 \cdot 3 < \dots
It is easy to see that d19=6739d_{19} = 673^9, d20=6739⋅3d_{20} = 673^9 \cdot 3 and n=d19⋅d20n = d_{19} \cdot d_{20}.

2. Let n=318⋅673n = 3^{18} \cdot 673, then
1<3<32<33<34<35<673<36<3⋅673<37<32⋅673<38<33⋅673<<39<34⋅673<310<35⋅673<311<36⋅673<312<… 1 < 3 < 3^2 < 3^3 < 3^4 < 3^5 < 673 < 3^6 < 3 \cdot 673 < 3^7 < 3^2 \cdot 673 < 3^8 < 3^3 \cdot 673 < \\ < 3^9 < 3^4 \cdot 673 < 3^{10} < 3^5 \cdot 673 < 3^{11} < 3^6 \cdot 673 < 3^{12} < \dots
It is easy to see that d19=36⋅673d_{19} = 3^6 \cdot 673, d20=312d_{20} = 3^{12} and n=d19⋅d20n = d_{19} \cdot d_{20}.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.