Maths Olympiad Prep

Track / Stage 5 / 366 of 400 #1446 of 2444

Problem 1446

AIME late
Number theory Difficulty 5.9 Prove it Austria competition problems · Austria · 2014

For any positive integer nn, let d(n)d(n) denote the number of divisors of nn including 11 and nn itself. For which values of nn is d(t)d(t) a divisor of d(n)d(n) for every divisor tt of nn?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

We show that this is the case if and only if nn is square-free, i.e. if nn contains no prime factor in a power greater than 11. In order to see this, write
n=j=1rpjej,and therefored(n)=j=1r(ej+1). n = \prod_{j=1}^{r} p_j^{e_j}, \quad \text{and therefore} \quad d(n) = \prod_{j=1}^{r} (e_j + 1).
If all powers eje_j are equal to 11, we have d(n)=2rd(n) = 2^r. In this case, every divisor tt of nn can also be written as the product of ss distinct primes (with 0sr0 \le s \le r), and therefore d(t)=2sd(t) = 2^s, which is certainly a divisor of d(n)=2rd(n) = 2^r.

We now assume that at least one value of eje_j is greater than one, without loss of generality, let this be ere_r. We now consider the divisor t=npr=prer1j=1r1(ej+1)t = \frac{n}{p_r} = p_r^{e_r-1} \cdot \prod_{j=1}^{r-1}(e_j+1). For this divisor, we have d(t)=erj=1r1(ej+1)d(t) = e_r \cdot \prod_{j=1}^{r-1}(e_j+1). In this case, we have d(n)d(t)=er+1er=1+1er\frac{d(n)}{d(t)} = \frac{e_r+1}{e_r} = 1 + \frac{1}{e_r}, which is certainly not an integer, and our proof is complete. \square

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.