Maths Olympiad Prep

Library / /18 of 34

, 2014

Number theory Difficulty 5.9 AIME, harder Prove it Austria

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?

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

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.