Olympiad Maths Prep

Library / /46 of 60

Number theory Difficulty 6.5 National olympiad Prove it Ukraine

Find the biggest three-digit number nn, for which the following condition is true: there exist exactly 16 pairs of natural numbers (a,b)(a, b), where a<ba < b, for which nn is the least common multiple.

Solution

At first suppose, that number n=p1m1pkmkn = p_1^{m_1} \dots p_k^{m_k}, where pip_i, i=1,ki = 1, \overline{k} – are distinct prime numbers and mim_i – are natural numbers, i=1,ki = 1, \overline{k}. Then let's choose all ordered pairs of numbers (a,b)(a, b), for which [a,b]=n[a, b] = n. Here we do not have condition a<ba < b, so pairs (a,b)(a, b) and (b,a)(b, a) for aba \neq b are considered different. If a=p1a1pkaka = p_1^{a_1} \dots p_k^{a_k} and b=p1b1pkbkb = p_1^{b_1} \dots p_k^{b_k}, so for satisfying condition [a,b]=n[a, b] = n it is necessary and sufficient that i=1,kmax{ai,bi}=mi\forall i = 1, \overline{k} \max\{a_i, b_i\} = m_i. Then possible variants of pairs (ai,bi)(a_i, b_i):
(0,mi),(1,mi),,(mi1,mi),(mi,mi),(mi,mi1),(mi,mi2),,(mi,0).(0, m_i), (1, m_i), \dots, (m_i - 1, m_i), (m_i, m_i), (m_i, m_i - 1), (m_i, m_i - 2), \dots, (m_i, 0).
In total there are 2mi+12m_i + 1 variants. So, in total there will be exactly N=(2m1+1)(2mk+1)N = (2m_1 + 1) \dots (2m_k + 1) ordered pairs of numbers. And there are exactly 12(N1)\frac{1}{2}(N-1) pairs, for which a<ba < b. Really, for all computed pairs we need to delete pair (n,n)(n, n), and for every two pairs (a,b)(a, b) and (b,a)(b, a) we need to leave one. So, we need to find the biggest three-digit natural number, for which 12(N1)=16\frac{1}{2}(N-1) = 16.

Then N=33N = 33, so there are two possible variants: N=216+1N = 2 \cdot 16 + 1 or N=(25+1)(21+1)N = (2 \cdot 5 + 1)(2 \cdot 1 + 1). In first case, for some prime pp condition is true n=p16216>999n = p^{16} \ge 2^{16} > 999. In second case, we have, that n=p5qn = p^5 q, where p,qp, q – are distinct prime numbers. As 55>9995^5 > 999, then p=2p = 2 or p=3p = 3.
For p=3p=3 we have, that 35=2433^5 = 243, so the number can only be 352=4863^5 \cdot 2 = 486, as 355>9993^5 \cdot 5 > 999.
For p=2p=2 we have, that 25=322^5 = 32, so the number can be maximum three-digit number of form: 25p2^5 \cdot p, where p>2p > 2 – is prime. As 1000:25=31.251000: 2^5 = 31.25, it is not hard to see, that the number is 2531=9922^5 \cdot 31 = 992.

Looking for a route rather than 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.