Maths Olympiad Prep

Library / /5 of 11

Algebra Difficulty 8.2 Shortlist Prove it Netherlands

Find all functions f:Z>0Z>0f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0} such that for all positive integers mm and nn it holds that
(f(m))2+2mf(n)+f(n2) (f(m))^2 + 2mf(n) + f(n^2)
is the square of an integer.

Solution

First, note that the function ι(m)=m\iota(m) = m is such a function, as
(ι(m))2+2mι(n)+ι(n2)=(m+n)2. (\iota(m))^2 + 2m\iota(n) + \iota(n^2) = (m+n)^2.

We show that ι\iota is the only such function.
Let ff be any such function. Substituting m=n=1m = n = 1, we see that f(1)2+3f(1)f(1)^2 + 3f(1) must be a square. As (f(1)+1)2f(1)2+3f(1)<(f(1)+2)2(f(1)+1)^2 \le f(1)^2 + 3f(1) < (f(1)+2)^2, the inequality on the left must be an equality, so f(1)=1f(1) = 1.

Now let kk be any positive integer for which p=2k+1p = 2k + 1 is an odd prime. By substituting m=k=12(p1)m = k = \frac{1}{2}(p-1) and n=1n = 1, we see that f(k)2+pf(k)^2 + p must be a square, say a2a^2 for a positive integer aa. Then p=a2f(k)2=(af(k))(a+f(k))p = a^2 - f(k)^2 = (a-f(k))(a+f(k)), so by unique factorisation and af(k)<a+f(k)a-f(k) < a+f(k) it follows that af(k)=1a-f(k) = 1 and a+f(k)=p=2k+1a+f(k) = p = 2k+1. Taking the difference of these two equalities yields f(k)=kf(k) = k.
Now let xx be any positive integer, and choose a positive integer kk for which p=2k+1p = 2k + 1 is an odd prime (so that f(k)=kf(k) = k) and that is large enough so that 12k2f(x)<f(x2)f(x)2<1+2k+2f(x)1-2k-2f(x) < f(x^2)-f(x)^2 < 1+2k+2f(x). Substituting m=km = k and n=xn = x then gives that k2+2kf(x)+f(x2)=(k+f(x))2+f(x2)f(x)2k^2+2kf(x)+f(x^2) = (k+f(x))^2+f(x^2)-f(x)^2 must be a square. By our chosen bound on kk, we have
(k+f(x)1)2<(k+f(x))2+f(x2)f(x)2<(k+f(x)+1)2. (k + f(x) - 1)^2 < (k + f(x))^2 + f(x^2) - f(x)^2 < (k + f(x) + 1)^2.
The expression in the middle is a square and therefore must equal (k+f(x))2(k+f(x))^2, therefore f(x2)=f(x)2f(x^2) = f(x)^2 for all positive integers xx.

Finally, let xx be any positive integer, and choose a positive integer kk for which p=2k+1p = 2k + 1 is again an odd prime and that is large enough so that 12x2k<(f(x))2x2<1+2x+2k1-2x-2k < (f(x))^2 - x^2 < 1+2x+2k. Substituting m=xm = x and n=kn = k then gives that (f(x))2+2xk+k2=(x+k)2+(f(x))2x2(f(x))^2 + 2xk + k^2 = (x+k)^2 + (f(x))^2 - x^2 must be a square. By our chosen bound on kk, we have
(x+k1)2<(x+k)2+(f(x))2x2<(x+k+1)2. (x + k - 1)^2 < (x + k)^2 + (f(x))^2 - x^2 < (x + k + 1)^2.
The expression in the middle is a square and therefore must equal (x+k)2(x+k)^2, therefore (f(x))2=x2(f(x))^2 = x^2 for all positive integers xx.
Thus f(x)=xf(x) = x for all positive integers xx, so ff must be equal to ι\iota. Therefore ι\iota is the only function satisfying the required property. ☐

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 reproduced verbatim; metadata (topic, difficulty) added by this project.