Maths Olympiad Prep

Library / /32 of 53

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(2232p)=332d(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=2a3b+1p1k1pmkmn = 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,
2a13b1p1k1pmkm=(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
2a13b1<(a+1)(b+2) 2^{a-1} \cdot 3^{b-1} < (a+1)(b+2)
or
f(a)=2a1a+1<b+23b1=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 a6a \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 b4b \ge 4. Thus 1\textcircled{1} holds only if b3b \le 3.

If b=3b=3, then (a,b)=(1,3)(a, b) = (1, 3), and 1\textcircled{1} becomes
9p1k1pmkm=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+152\frac{p_1^{k_1}}{k_1+1} = \frac{5^{k_1}}{k_1+1} \ge \frac{5}{2} for positive integer k11k_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
32a1p1k1pmkm=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 2a12^{a-1} or a3a \ge 3. Hence aa must be equal to 33. But then 4(a+1)=164(a+1) = 16 divides 2a12^{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
2a1p1k1pmkm=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 and solution reproduced as published; topic and difficulty added by this site.