Olympiad Maths Prep

Library / /8 of 11

Number theory Difficulty 6.3 National olympiad Prove it Czech Republic

**Find all functions f:NNf: \mathbb{N} \to \mathbb{N} such that for every positive integer mm the following is true: If we denote by d1,d2,,dnd_1, d_2, \dots, d_n all the divisors of number mm then**
f(d1)f(d2)f(dn)=m. f(d_1) \cdot f(d_2) \cdots f(d_n) = m.

Solution

We will show that the only solution is a function ff such that
f(m)={p,if m is a non-trivial power of a prime p, i.e. m=pk,k1,1,otherwise. f(m) = \begin{cases} p, & \text{if } m \text{ is a non-trivial power of a prime } p, \text{ i.e. } m = p^k, k \ge 1, \\ 1, & \text{otherwise.} \end{cases}
Number 11 has the unique divisor 11, hence plugging m=1m = 1 in the given equality we get f(1)=1f(1) = 1.
Let m=pm = p be a prime. Then
f(1)f(p)=pi.e.f(p)=p. f(1) \cdot f(p) = p \quad \text{i.e.} \quad f(p) = p.
For m=p2m = p^2 we get
f(1)f(p)f(p2)=p2i.e.f(p2)=p f(1) \cdot f(p) \cdot f(p^2) = p^2 \quad \text{i.e.} \quad f(p^2) = p
and in general for k>1k > 1 and m=pkm = p^k
f(1)f(p)f(p2)f(pk)=pk. f(1) \cdot f(p) \cdot f(p^2) \cdots f(p^k) = p^k.
By induction, f(pk)=pf(p^k) = p for all positive integers kk.
Now let us consider positive integer mm with at least two distinct prime factors whose factorization is m=p1α1p2α2pkαkm = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}, where k2k \ge 2 and αi1\alpha_i \ge 1 for every i{1,2,,k}i \in \{1, 2, \dots, k\}. The divisors of mm include the powers
p1,p12,,p1α1,p2,p22,,p2α2,,pk,pk2,,pkαk, p_1, p_1^2, \dots, p_1^{\alpha_1}, p_2, p_2^2, \dots, p_2^{\alpha_2}, \dots, p_k, p_k^2, \dots, p_k^{\alpha_k},
of its prime factors but the product of the corresponding function values
f(p1)f(p12)f(p1α1)f(p2)f(p22)f(p2α2)f(pk)f(pk2)f(pkαk)=p1p1p1α1p2p2p2α2pkpkpkαk=p1α1p2α2pkαk=m \begin{aligned} & f(p_1)f(p_1^2)\dots f(p_1^{\alpha_1})f(p_2)f(p_2^2)\dots f(p_2^{\alpha_2})\dots f(p_k)f(p_k^2)\dots f(p_k^{\alpha_k}) \\ &= \underbrace{p_1p_1\dots p_1}_{\alpha_1} \underbrace{p_2p_2\dots p_2}_{\alpha_2} \dots \underbrace{p_kp_k\dots p_k}_{\alpha_k} = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k} = m \end{aligned}
yields mm. This means that the product of all the other function values (none of which is a non-trivial power of a prime), including f(m)f(m), is equal to 11 so all the other function values, including f(m)f(m), are equal to 11.
This specifies ff uniquely and also shows that it has the desired properties.

Looking for a route rather than 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.