Maths Olympiad Prep

Library / /34 of 52

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=d19d20n = d_{19} \cdot d_{20}.

Solution

Answer: n=367318n = 3 \cdot 673^{18}; n=318673n = 3^{18} \cdot 673.

Note that the equality n=d19d20n = d_{19} \cdot d_{20} implies that nn has exactly 3838 divisors. Indeed,
n=d19d20=d18d21=d17d22==d1d38=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=pq18n = p \cdot q^{18} or n=p18qn = p^{18} \cdot q, respectively.

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

1. Let n=367318n = 3 \cdot 673^{18}. Arrange the divisors in an ascending order:
1<3<673<6733<6732<67323<<6739<67393< 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=67393d_{20} = 673^9 \cdot 3 and n=d19d20n = d_{19} \cdot d_{20}.

2. Let n=318673n = 3^{18} \cdot 673, then
1<3<32<33<34<35<673<36<3673<37<32673<38<33673<<39<34673<310<35673<311<36673<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=36673d_{19} = 3^6 \cdot 673, d20=312d_{20} = 3^{12} and n=d19d20n = d_{19} \cdot d_{20}.

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.