Maths Olympiad Prep

Library / Czech and Slovak Mathematical Olympiad /44 of 70

Czech and Slovak Mathematical Olympiad

Number theory Difficulty 6.3 National Olympiad Prove it Czech Republic

**Find all functions f:N→Nf: \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,k≥1,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α2…pkαkm = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}, where k≥2k \ge 2 and αi≥1\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)=p1p1…p1⏟α1p2p2…p2⏟α2…pkpk…pk⏟αk=p1α1p2α2…pkα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.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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