Maths Olympiad Prep

Library / /16 of 63

Algebra Difficulty 6.4 National olympiad Prove it Japan

Let NN denote the set of positive integers. Find all functions f:NNf : N \to N such that the equation
lcm(m,f(m+f(n)))=lcm(f(m),f(m)+n) \operatorname{lcm}(m, f(m + f(n))) = \operatorname{lcm}(f(m), f(m) + n)
holds for any positive integers mm and nn. Here, for positive integers xx and yy, lcm(x,y)\operatorname{lcm}(x, y) denotes their least common multiple.

Solution

We prove that the function f(n)=nf(n) = n is the unique function satisfying the condition in the problem. It is easy to see that this ff satisfies the condition in the problem.

Suppose that ff is the function that satisfies the condition in the problem. First, for any positive integer kk, we prove that f(k)f(k) is a multiple of kk. Let rr be the remainder when dividing f(k)f(k) by kk. Substituting m=km = k and n=kr+1n = k - r + 1 into the equation in the problem, we obtain
lcm(k,f(k+f(kr+1)))=lcm(f(k),f(k)+kr+1). \operatorname{lcm}(k, f(k + f(k - r + 1))) = \operatorname{lcm}(f(k), f(k) + k - r + 1).
Therefore, lcm(f(k),f(k)+kr+1)\operatorname{lcm}(f(k), f(k) + k - r + 1) is a multiple of kk. Here, f(k)+kr+1f(k) + k - r + 1 leaves a remainder of 11 when divided by kk, and hence, f(k)+kr+1f(k) + k - r + 1 is coprime to kk. Therefore, we conclude that f(k)f(k) is a multiple of kk.

Let mm be a positive integer. We prove that f(m)=mf(m) = m. Substituting n=f(m)n = f(m) into the equation in the problem, we get
lcm(m,f(m+f(f(m))))=lcm(f(m),2f(m))=2f(m). \operatorname{lcm}(m, f(m + f(f(m)))) = \operatorname{lcm}(f(m), 2f(m)) = 2f(m).
Therefore, 2f(m)2f(m) is a multiple of f(m+f(f(m)))f(m + f(f(m))). Since f(m+f(f(m)))f(m + f(f(m))) is a multiple of m+f(f(m))m + f(f(m)), 2f(m)2f(m) is a multiple of m+f(f(m))m + f(f(m)). Note that we have
2f(m)2f(f(m))<2(m+f(f(m))). 2f(m) \le 2f(f(m)) < 2(m + f(f(m))).
Here, the first inequality follows from the fact that f(f(m))f(f(m)) is a multiple of f(m)f(m). Therefore, we conclude that 2f(m)=m+f(f(m))2f(m) = m + f(f(m)). Since
f(f(m))=2f(m)m<2f(m) f(f(m)) = 2f(m) - m < 2f(m)
and f(f(m))f(f(m)) is a multiple of f(m)f(m), we conclude that f(f(m))=f(m)f(f(m)) = f(m). Hence, we have 2f(m)=m+f(m)2f(m) = m + f(m), and hence f(m)=mf(m) = m. We complete the proof.

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.