Maths Olympiad Prep

Library / /3 of 6

Algebra Difficulty 8.4 Shortlist Prove it Germany

Problem:

Let Z+\mathbb{Z}^{+} be the set of positive integers.
Determine all functions f:Z+Z+f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} with the property that for all positive integers mm and nn the following holds: m2+f(n)mf(m)+nm^{2}+f(n) \mid m f(m)+n.

Solution

Solution:

For an arbitrary positive integer nn we choose mm such that f(n)mf(n) \mid m holds. Then it follows that f(n)m2+f(n)f(n) \mid m^{2}+f(n) and f(n)mf(m)+nf(n) \mid m f(m)+n. Since mm is divisible by f(n)f(n), nn must also be divisible by f(n)f(n). Thus we have f(n)nf(n) \mid n, which means f(n)nf(n) \leq n for all nZ+n \in \mathbb{Z}^{+}.

In particular this yields f(1)1f(1) \mid 1, hence f(1)=1f(1)=1.

We further assume that there exists an mZ+m \in \mathbb{Z}^{+} with f(m)<mf(m)<m. With n=1n=1 we obtain m2+1mf(m)+1m^{2}+1 \mid m f(m)+1, but on the other hand we then have 0<mf(m)+1<m2+10<m f(m)+1<m^{2}+1, so that m2+1m^{2}+1 cannot divide mf(m)+1m f(m)+1 - contradiction! Hence f(m)mf(m) \geq m holds, and combined with the above it follows that f(n)=nf(n)=n for all nZ+n \in \mathbb{Z}^{+}.

Substituting confirms via n2+n=n2+f(n)nf(n)+n=n2+nn^{2}+n=n^{2}+f(n) \mid n f(n)+n=n^{2}+n that this function is indeed - therefore - the only solution.

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 translated into English from de; metadata (topic, difficulty) added by this project.