Austria 2014

Question

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

Accepted Answer

We show that this is the case if and only if

n

is square-free, i.e. if

n

contains no prime factor in a power greater than

1

. In order to see this, write

n = j = 1 \prod r p_{j}^{e_{j}}, and therefore d (n) = j = 1 \prod r (e_{j} + 1) .

If all powers

e_{j}

are equal to

1

, we have

d (n) = 2^{r}

. In this case, every divisor

t

of

n

can also be written as the product of

s

distinct primes (with

0 \leq s \leq r

), and therefore

d (t) = 2^{s}

, which is certainly a divisor of

d (n) = 2^{r}

.

We now assume that at least one value of

e_{j}

is greater than one, without loss of generality, let this be

e_{r}

. We now consider the divisor

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) = e_{r} \cdot \prod_{j = 1}^{r - 1} (e_{j} + 1)

. In this case, we have

\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.

□