Maths Olympiad Prep

Library / /132 of 144

Number theory Difficulty 8.8 Shortlist Find the answer

For every nN n\in\mathbb{N} let d(n) d(n) denote the number of (positive) divisors of n n. Find all functions f:NN f: \mathbb{N}\to\mathbb{N} with the following properties:
- d (f(x) ) x\text{d (f(x) ) x} for all xN x\in\mathbb{N}.

- f(xy) f(xy) divides (x 1)y xy 1 f(x)\text{(x 1)y xy 1 f(x)} for all x x, yN y\in\mathbb{N}.

*

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Given the function f:NN f: \mathbb{N} \to \mathbb{N} with specified properties, we aim to determine all possible forms of f f .

The properties are:
1. d(f(x))=x d(f(x)) = x for all xN x \in \mathbb{N} .
2. f(xy) f(xy) divides (x1)yxy1f(x) (x - 1)y^{xy - 1}f(x) for all x,yN x, y \in \mathbb{N} .

### Analysis of the First Property

The first property indicates that f(x) f(x) must be a number with exactly x x positive divisors. For a natural number n n , if its prime factorization is given by n=p1b1p2b2pkbk n = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} , then the number of divisors d(n) d(n) is given by:
d(n)=(b1+1)(b2+1)(bk+1). d(n) = (b_1 + 1)(b_2 + 1)\cdots(b_k + 1).
For d(f(x))=x d(f(x)) = x , we need:
(b1+1)(b2+1)(bk+1)=x. (b_1 + 1)(b_2 + 1)\cdots(b_k + 1) = x.

### Structure of f(x) f(x)

Considering integers with exactly x x divisors, a suitable candidate for f(x) f(x) would be a number constructed from powers of distinct prime numbers, ensuring that the product of incremented exponents matches x x .

### Analysis of the Second Property

The second property says that:
f(xy)(x1)yxy1f(x). f(xy) \mid (x - 1)y^{xy - 1}f(x).

It implies that, under multiplication, the divisibility structure must be preserved. Part of checking this is ensuring f(xy)(x1)yxy1f(x) f(xy) \leq (x-1) y^{xy-1} f(x) .

### Hypothesizing a Solution

From condition (1) and upon logical construction, a common strategy is setting f(x) f(x) as:
f(x)=i=1kpixi f(x) = \prod_{i=1}^k p_i^{x_i}
where pi p_i are distinct primes and xi x_i are chosen such that:
(x1+1)(x2+1)(xk+1)=x. (x_1 + 1)(x_2 + 1)\cdots(x_k + 1) = x.

To further satisfy condition (2), the arrangement and selection of xi x_i need to ensure f(xy) f(xy) constructs similarly and divides the expression given on the right side.

One such explicit formulation that satisfies our constraints aligns with:
f(n)=i=1kpipiαi1 f(n) = \prod_{i=1}^k p_i^{p_i^{\alpha_i} - 1}
where αi\alpha_i are chosen such that the product of (αi+1)(\alpha_i+1) equals n n , leveraging the flexibility in selecting prime bases.

### Conclusion

Hence, the form of the function f(n) f(n) consistent with the given properties and the reference answer is:
i=1kpipiαi1 \boxed{\prod_{i=1}^k p_i^{p_i^{\alpha_i} - 1}}
where αi \alpha_i and pi p_i are structured appropriately to ensure d(f(n))=n d(f(n)) = n .

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