Maths Olympiad Prep

Library / /30 of 36

, 2023

Number theory Difficulty 8.8 Shortlist Prove it Baltic Way

Let Z+\mathbb{Z}^+ denote the set of positive integers, and lcm(n,m)\text{lcm}(n, m) the least positive integer that is divisible by both nn and mm.
Find all functions f:Z+Z+f: \mathbb{Z}^+ \to \mathbb{Z}^+ such that
lcm(nf(n2),f(m2))=nf(nm), for all positive integers n,m \text{lcm}(n \cdot f(n^2), f(m^2)) = n \cdot f(nm), \text{ for all positive integers } n, m
and such that f(n)f(n) divides nn for all positive integers nn.

Solution

First notice that f(1)f(1) divides 11, and hence f(1)=1f(1) = 1. For all primes pp, we have
pf(p2n)=lcm(pf(p2n),1)=lcm(pf(p2n),f(12))=pf(pn1)=pf(pn), \begin{align*} p \cdot f(p^{2n}) &= \text{lcm}(p \cdot f(p^{2n}), 1) = \text{lcm}(p \cdot f(p^{2n}), f(1^2)) \\ &= p \cdot f(p^n \cdot 1) = p \cdot f(p^n), \end{align*}
which shows that f(pn)=f(p2n)f(p^n) = f(p^{2n}) for all nn. Now we show by induction on mm that f(pm)=f(p)f(p^m) = f(p). We know that f(p2)=f(p)f(p^2) = f(p). Assume that f(pm)=f(p)f(p^m) = f(p). Now
pf(ppm)=lcm(pf(p2),f(p2m))=lcm(pf(p),f(pm))=pf(p),and hence f(pm+1)=f(p). \begin{gather*} p f(p \cdot p^m) = \text{lcm}(p \cdot f(p^2), f(p^{2m})) = \text{lcm}(p \cdot f(p), f(p^m)) = p \cdot f(p), \\ \text{and hence } f(p^{m+1}) = f(p). \end{gather*}
Since f(p)f(p) divides pp, we know that f(p)=pαpf(p) = p^{\alpha_p} for αp{0,1}\alpha_p \in \{0, 1\}. For each prime pip_i, let f(pi)=piαpif(p_i) = p_i^{\alpha_{p_i}} with αpi{0,1}\alpha_{p_i} \in \{0, 1\}. For two primes p1p2p_1 \neq p_2, we have
p1nf(p1np2m)=lcm(p1nf(p12n),f(p22m))=lcm(p1np1αp1,p2αp2)=p1np1αp1p2αp2, \begin{align*} p_1^n f(p_1^n \cdot p_2^m) &= \text{lcm}(p_1^n \cdot f(p_1^{2n}), f(p_2^{2m})) = \text{lcm}(p_1^n \cdot p_1^{\alpha_{p_1}}, p_2^{\alpha_{p_2}}) \\ &= p_1^n \cdot p_1^{\alpha_{p_1}} \cdot p_2^{\alpha_{p_2}}, \end{align*}
and hence f(p1np2m)=p1αp1p2αp2f(p_1^n \cdot p_2^m) = p_1^{\alpha_{p_1}} \cdot p_2^{\alpha_{p_2}} for all non-negative integers nn and mm. By induction on rr, it follows that
f(p1n1p2n2prnr)=p1αp1p2αp2prαpr. f(p_1^{n_1} p_2^{n_2} \cdots p_r^{n_r}) = p_1^{\alpha_{p_1}} p_2^{\alpha_{p_2}} \cdots p_r^{\alpha_{p_r}}.

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.