Olympiad Maths Prep

Track / Stage 5 / 8 of 400 #608 of 2000

Problem 608

AIME late
Number theory Difficulty 5.0 Find the answer

1. Find all functions f:Z+Z+f: \mathbf{Z}_{+} \rightarrow \mathbf{Z}_{+}, such that for all positive integers m,nm, n, we have
(m2+f(n))(mf(m)+n). \left(m^{2}+f(n)\right) \mid(m f(m)+n) .

Official solution

1. The function f(n)=nf(n)=n satisfies the condition.

Let m=n=2m=n=2. Then
(4+f(2))(2f(2)+2) (4+f(2)) \mid(2 f(2)+2) \text {. }

Since 2f(2)+2<2(4+f(2))2 f(2)+2<2(4+f(2)), we have
2f(2)+2=4+f(2) 2 f(2)+2=4+f(2) \text {. }

Thus, f(2)=2f(2)=2.
Let m=2m=2. Then (4+f(n))(4+n)(4+f(n)) \mid(4+n).
This indicates that for any positive integer nn, we have f(n)nf(n) \leqslant n.
Let m=nm=n. Then
(n2+f(n))(nf(n)+n)nf(n)+nn2+f(n)(n1)(f(n)n)0. \begin{array}{l} \left(n^{2}+f(n)\right) \mid(n f(n)+n) \\ \Rightarrow n f(n)+n \geqslant n^{2}+f(n) \\ \Rightarrow(n-1)(f(n)-n) \geqslant 0 . \end{array}

This indicates that for all positive integers n2n \geqslant 2, we have f(n)nf(n) \geqslant n, and the conclusion also holds when n=1n=1.
Therefore, for all positive integers nn, we have 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.