Maths Olympiad Prep

Library / /401 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

Example 9. Let f(n)f(n) be a strictly increasing function defined on the set of natural numbers and taking natural number values, with f(2)=2f(2)=2, and when mm, nn are coprime, f(mn)=f(m)f(n)f(m n)=f(m) f(n). Prove that for all natural numbers nn, f(n)=nf(n)=n.

Solution

Proof Given that
f(3)f(7)=f(21)f(2)=2, hence f(3)=3. \begin{aligned} f(3) f(7) & =f(21)f(2)=2, \text{ hence } f(3)=3. \end{aligned}
If the proposition is not true, let the smallest positive integer for which f(n)nf(n) \neq n be n04n_{0} \geqslant 4. Since f(n0)>f(n01)=n01f\left(n_{0}\right)>f\left(n_{0}-1\right)=n_{0}-1, it follows that f(n0)>n0f\left(n_{0}\right)>n_{0}. Furthermore, because f(n)f(n) is strictly increasing, we have
f(n)>n, when nn0 f(n)>n \text{, when } n \geqslant n_{0} \text{. }

When n0n_{0} is odd, 2 and n02n_{0}-2 are coprime, so we have
f(2(n02))=f(2)f(n02)=2(n02). \begin{aligned} f\left(2\left(n_{0}-2\right)\right) & =f(2) f\left(n_{0}-2\right) \\ & =2\left(n_{0}-2\right) . \end{aligned}

Since n04n_{0} \geqslant 4, it follows that 2(n02)n02\left(n_{0}-2\right) \geqslant n_{0}, which contradicts (1). When n0n_{0} is even, 2 and n01n_{0}-1 are coprime, so we have
f(2(n01))=f(2)f(n01)=2(n01). \begin{aligned} f\left(2\left(n_{0}-1\right)\right) & =f(2) f\left(n_{0}-1\right) \\ & =2\left(n_{0}-1\right) . \end{aligned}

Clearly, 2(n01)>n02\left(n_{0}-1\right)>n_{0}, which contradicts (1).

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