Olympiad Maths Prep

Track / Stage 5 / 343 of 400 #943 of 2000

Problem 943

AIME late
Number theory Difficulty 5.8 Prove it

Example 2 Let {f(n)}\{f(n)\} be a strictly increasing sequence of positive integers. It is known that f(2)=2f(2)=2, and when m,nm, n are coprime,
f(mn)=f(m)f(n) f(m n)=f(m) f(n) \text {. }

Prove: f(n)=nf(n)=n.
(24th Putnam Mathematical Competition A2\mathrm{A}-2)

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

To prove: The problem is to prove that f(n)f(n) is a fixed point for any natural number n(n2)n (n \geqslant 2) under the given conditions. In fact,
f(3)f(7)=f(21)f(2)=2, so, f(3)=3. \begin{array}{l} f(3) f(7)=f(21) \\ f(2)=2, \text{ so, } f(3)=3. \end{array}
We will prove this by contradiction.
If the original proposition is not true, assume the smallest positive integer nn for which f(n)nf(n) \neq n is n04n_{0} \geqslant 4, then
f(n0)>f(n01)=n01. f\left(n_{0}\right)>f\left(n_{0}-1\right)=n_{0}-1.

Therefore, it can only be that f(n0)>n0f\left(n_{0}\right)>n_{0}.
Also, {f(n)}\{f(n)\} is strictly increasing, so when nn0n \geqslant n_{0}, we have
f(n)>n. f(n)>n.

We will discuss this in two cases:
(1) When n0n_{0} is odd, 2 and n02n_{0}-2 are coprime, then
f[2(n02)]=f(2)f(n02)=2(n02). \begin{array}{l} f\left[2\left(n_{0}-2\right)\right]=f(2) f\left(n_{0}-2\right) \\ =2\left(n_{0}-2\right). \end{array}

Since n04n_{0} \geqslant 4, then 2(n02)n02\left(n_{0}-2\right) \geqslant n_{0}. Thus, equation (2) contradicts equation (1).
(2) When n0n_{0} is even, 2 and n01n_{0}-1 are coprime, similarly, we have
f[2(n01)]=f(2)f(n01)=2(n01). \begin{array}{l} f\left[2\left(n_{0}-1\right)\right]=f(2) f\left(n_{0}-1\right) \\ =2\left(n_{0}-1\right). \end{array}

Since n04n_{0} \geqslant 4, then 2(n01)n02\left(n_{0}-1\right) \geqslant n_{0}. Thus, equation (3) contradicts equation (1).
In summary, equation (1) does not hold. Therefore, f(n)=nf(n)=n.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.