Maths Olympiad Prep

Library / /477 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Example 28([39.3]) For any positive integer nn, let d(n)d(n) denote the number of all positive divisors (including 1 and nn) of nn. Determine all possible positive integers kk such that there exists a positive integer nn satisfying: d(n2)/d(n)=kd\left(n^{2}\right) / d(n)=k.

---

The translation maintains the original text's formatting and structure.

Solution

(i) Let n=p1a(1)pra(r)n=p_{1}^{a(1)} \cdots p_{r}^{a(r)}, we have
k=d(n2)/d(n)=(1+2a(1))(1+2a(r))/[(1+a(1))(1+a(r))]\begin{aligned} k & =d\left(n^{2}\right) / d(n) \\ & =(1+2 a(1)) \cdots(1+2 a(r)) /[(1+a(1)) \cdots(1+a(r))] \end{aligned}

Thus, kk must be an odd number. Therefore, nn must be a perfect square.
(ii) Now we prove that any odd number kk can be expressed in this way. We use induction. When k=1k=1, we can take n=1n=1; when k=3k=3, we can take n=(232)2n=\left(2 \cdot 3^{2}\right)^{2}. Hence, the conclusion holds for k=1,3k=1,3. Assume that for all positive odd numbers k4N+3(N0)k \leqslant 4 N+3(N \geqslant 0), the conclusion holds. We will prove that for all positive odd numbers k4(N+1)+3k \leqslant 4(N+1)+3, the conclusion holds. This requires considering two cases.
(a) When k=4(N+1)+1k=4(N+1)+1, by the induction hypothesis and the fact that nn must be a perfect square, there exists n1n_{1} such that 1+2(N+1)=d(n14)/d(n12)1+2(N+1)=d\left(n_{1}^{4}\right) / d\left(n_{1}^{2}\right). Now take n=n12p2(N+1)n=n_{1}^{2} p^{2(N+1)}, where the prime pp is coprime with n1n_{1}. We then have
k=4(N+1)+1=d(n2)/d(n)k=4(N+1)+1=d\left(n^{2}\right) / d(n)
(b) When k=4(N+1)+3k=4(N+1)+3, we have k=2lm1,(2,m)=1,l2k=2^{l} m-1,(2, m)=1, l \geqslant 2. By the induction hypothesis and the fact that nn must be a perfect square, there exists n1n_{1} such that m=d(n14)/d(n12)m=d\left(n_{1}^{4}\right) / d\left(n_{1}^{2}\right). Take distinct primes p1,,plp_{1}, \cdots, p_{l}, all coprime with n1n_{1}, and let 2β(j)=3j2ljm2(1jl1)2 \beta(j)=3^{j} 2^{l-j} m-2(1 \leqslant j \leqslant l-1), 2β(l)=3l1m12 \beta(l)=3^{l-1} m-1, n=n1p1β(1)plβ(l)n=n_{1} p_{1}^{\beta(1)} \cdots p_{l}^{\beta(l)}. We then have
k=4(N+1)+3=d(n2)/d(n)k=4(N+1)+3=d\left(n^{2}\right) / d(n)

Therefore, for all positive odd numbers k4(N+1)+3k \leqslant 4(N+1)+3, the conclusion holds. Proof completed.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.