Maths Olympiad Prep

Library / /31 of 55

Number theory Difficulty 6.4 National Olympiad Prove it China

A positive integer mm is called good, if there is a positive integer nn such that mm is the quotient of nn over the number of positive integer divisors of nn (including 1 and nn itself). Prove that 1,2,…,171, 2, \ldots, 17 are good numbers and that 1818 is not a good number.

Solution

For positive integer nn, let d(n)d(n) denote the number of positive divisors of nn (including 11 and nn itself).

Firstly, note that 11 and 22 are good, since 1=2d(2)1 = \frac{2}{d(2)} and
2=8d(8). 2 = \frac{8}{d(8)}.

Secondly, we note that if pp is an odd prime, then pp is good. This is because d(8p)=8d(8p) = 8. In particular, 3,5,7,11,13,173, 5, 7, 11, 13, 17 are good numbers.

Thirdly, we note that if pp is an odd prime, then 2p2p is good. This is because d(22⋅32p)=3⋅3⋅2d(2^2 \cdot 3^2 p) = 3 \cdot 3 \cdot 2. In particular, 6,10,146, 10, 14 are good numbers.

Fourthly, we note that
4=36d(36),8=96d(96),9=108d(108), 4 = \frac{36}{d(36)}, \quad 8 = \frac{96}{d(96)}, \quad 9 = \frac{108}{d(108)},
12=240d(240),15=360d(360),16=128d(128). 12 = \frac{240}{d(240)}, \quad 15 = \frac{360}{d(360)}, \quad 16 = \frac{128}{d(128)}.
Thus, the numbers 1,2,…,171, 2, \ldots, 17 are good.

Finally, we prove that 1818 is not good. We approach indirectly by assuming that 18=nd(n)18 = \frac{n}{d(n)} or n=18d(n)n = 18 d(n) for n=2a⋅3b+1⋅p1k1⋯pmkmn = 2^a \cdot 3^{b+1} \cdot p_1^{k_1} \cdots p_m^{k_m} (where p1<⋯<pmp_1 < \cdots < p_m are prime numbers greater than 33 and a,b,k1,⋯ ,kma, b, k_1, \cdots, k_m are positive integers); that is,
2a−1⋅3b−1⋅p1k1⋯pmkm=(a+1)(b+2)(k1+1)⋯(km+1).1◯ 2^{a-1} \cdot 3^{b-1} \cdot p_1^{k_1} \cdots p_m^{k_m} = (a+1)(b+2)(k_1+1)\cdots(k_m+1). \qquad \textcircled{1}
For every odd prime pp and every positive integer kk, we can show (by an easy induction on kk) that
pk>k+1.2◯ p^k > k+1. \qquad \textcircled{2}
Combining the last two relations, we deduce that
2a−1⋅3b−1<(a+1)(b+2) 2^{a-1} \cdot 3^{b-1} < (a+1)(b+2)
or
f(a)=2a−1a+1<b+23b−1=g(b). f(a) = \frac{2^{a-1}}{a+1} < \frac{b+2}{3^{b-1}} = g(b).
It is easy to prove that f(1)=12f(1) = \frac{1}{2}, f(2)=23f(2) = \frac{2}{3}, f(3)=1f(3) = 1, f(4)=85f(4) = \frac{8}{5}, f(5)=166f(5) = \frac{16}{6}, and f(a)≥327>4f(a) \ge \frac{32}{7} > 4 for a≥6a \ge 6. It is also easy to prove that g(1)=3g(1) = 3, g(2)=43g(2) = \frac{4}{3}, g(3)<59g(3) < \frac{5}{9}, and g(b)<29g(b) < \frac{2}{9} for b≥4b \ge 4. Thus 1◯\textcircled{1} holds only if b≤3b \le 3.

If b=3b=3, then (a,b)=(1,3)(a, b) = (1, 3), and 1◯\textcircled{1} becomes
9p1k1⋯pmkm=10(k1+1)⋯(km+1), 9p_1^{k_1} \cdots p_m^{k_m} = 10(k_1 + 1)\cdots(k_m + 1),
implying that p1=5p_1 = 5. Since 2◯\textcircled{2} and p1k1k1+1=5k1k1+1≥52\frac{p_1^{k_1}}{k_1+1} = \frac{5^{k_1}}{k_1+1} \ge \frac{5}{2} for positive integer k1≥1k_1 \ge 1, we can easily see that there is no solution in this case.

If b=2b=2, then (a,b)=(1,2)(a, b) = (1, 2), (2,2)(2, 2), (3,2)(3, 2), and 1◯\textcircled{1} becomes
3⋅2a−1p1k1⋯pmkm=4(a+1)(k1+1)⋯(km+1). 3 \cdot 2^{a-1} p_1^{k_1} \cdots p_m^{k_m} = 4(a+1)(k_1+1) \cdots (k_m+1).
We deduce that 44 divides 2a−12^{a-1} or a≥3a \ge 3. Hence aa must be equal to 33. But then 4(a+1)=164(a+1) = 16 divides 2a−12^{a-1}, which is impossible.

If b=1b=1, then (a,b)=(1,1)(a, b) = (1, 1), (2,1)(2, 1), (3,1)(3, 1), (4,1)(4, 1), (5,1)(5, 1), and 1◯\textcircled{1} becomes
2a−1p1k1⋯pmkm=3(a+1)(k1+1)⋯(km+1), 2^{a-1} p_1^{k_1} \cdots p_m^{k_m} = 3(a+1)(k_1+1) \cdots (k_m+1),
which is impossible since pip_i are primes greater than 33.

In all the cases, we cannot find nn satisfying the condition 18=nd(n)18 = \frac{n}{d(n)}; that is, 1818 is not a good number.

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.