Maths Olympiad Prep

Library / /12 of 48

Algebra Difficulty 7.0 National olympiad Prove it Asia Pacific Mathematics Olympiad (APMO)

Let Z+\mathbb{Z}^{+} be the set of positive integers. Determine all functions f:Z+Z+f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} such that a2+f(a)f(b)a^{2} + f(a) f(b) is divisible by f(a)+bf(a) + b for all positive integers aa and bb.

Solutions — 3

Solution 1

First we perform the following substitutions on the original relation:

1. With a=b=1a = b = 1, we find that f(1)+1f(1)2+1f(1) + 1 \mid f(1)^{2} + 1, which implies f(1)=1f(1) = 1.

2. With a=1a = 1, we find that b+1f(b)+1b + 1 \mid f(b) + 1. In particular, bf(b)b \leq f(b) for all bZ+b \in \mathbb{Z}^{+}.

3. With b=1b = 1, we find that f(a)+1a2+f(a)f(a) + 1 \mid a^{2} + f(a), and thus f(a)+1a21f(a) + 1 \mid a^{2} - 1. In particular, f(a)a22f(a) \leq a^{2} - 2 for all a2a \geq 2.

Now, let pp be any odd prime. Substituting a=pa = p and b=f(p)b = f(p) in the original relation, we find that 2f(p)p2+f(p)f(f(p))2 f(p) \mid p^{2} + f(p) f(f(p)). Therefore, f(p)p2f(p) \mid p^{2}. Hence the possible values of f(p)f(p) are 11, pp and p2p^{2}. By (2) above, f(p)pf(p) \geq p and by (3) above f(p)p22f(p) \leq p^{2} - 2. So f(p)=pf(p) = p for all primes pp.

Substituting a=pa = p into the original relation, we find that b+pp2+pf(b)b + p \mid p^{2} + p f(b). However, since (b+p)(f(b)+pb)=p2b2+bf(b)+pf(b)(b + p)(f(b) + p - b) = p^{2} - b^{2} + b f(b) + p f(b), we have b+pbf(b)b2b + p \mid b f(b) - b^{2}. Thus, for any fixed bb this holds for arbitrarily large primes pp and therefore we must have bf(b)b2=0b f(b) - b^{2} = 0, or f(b)=bf(b) = b, as desired.

Solution 2

As above, we have relations (1)-(3). In (2) and (3), for b=2b = 2 we have 3f(2)+13 \mid f(2) + 1 and f(2)+13f(2) + 1 \mid 3. These imply f(2)=2f(2) = 2.

Now, using a=2a = 2 we get 2+b4+2f(b)2 + b \mid 4 + 2 f(b). Let f(b)=xf(b) = x. We have
1+x0(modb+1)4+2x0(modb+2) \begin{array}{r} 1 + x \equiv 0 \quad (\bmod b + 1) \\ 4 + 2x \equiv 0 \quad (\bmod b + 2) \end{array}
From the first equation xb(modb+1)x \equiv b (\bmod b + 1) so x=b+(b+1)tx = b + (b + 1)t for some integer t0t \geq 0. Then
04+2x4+2(b+(b+1)t)4+2(2t)2t(modb+2) 0 \equiv 4 + 2x \equiv 4 + 2(b + (b + 1)t) \equiv 4 + 2(-2 - t) \equiv -2t \quad (\bmod b + 2)
Also tb2t \leq b - 2 because 1+xb211 + x \mid b^{2} - 1 by (3).

If b+2b + 2 is odd, then t0(modb+2)t \equiv 0 (\bmod b + 2). Then t=0t = 0, which implies f(b)=bf(b) = b.
If b+2b + 2 is even, then t0(mod(b+2)/2)t \equiv 0 (\bmod (b + 2)/2). Then t=0t = 0 or t=(b+2)/2t = (b + 2)/2. But if t0t \neq 0, then by definition (b+4)/2=(1+t)=(x+1)/(b+1)(b + 4)/2 = (1 + t) = (x + 1)/(b + 1) and since x+1b21x + 1 \mid b^{2} - 1, then (b+4)/2(b + 4)/2 divides b1b - 1. Therefore b+410b + 4 \mid 10 and the only possibility is b=6b = 6. So for even bb, b6b \neq 6 we have f(b)=bf(b) = b.

Finally, by (2) and (3), for b=6b = 6 we have 7f(6)+17 \mid f(6) + 1 and f(6)+135f(6) + 1 \mid 35. This means f(6)=6f(6) = 6 or f(6)=34f(6) = 34. The latter is discarded as, for a=5a = 5, b=6b = 6, we have by the original equation that 115(5+f(6))11 \mid 5(5 + f(6)). Therefore f(n)=nf(n) = n for every positive integer nn.

Solution 3

We proceed by induction. As in Solution 1, we have f(1)=1f(1) = 1. Suppose that f(n1)=n1f(n - 1) = n - 1 for some integer n2n \geq 2.

With the substitution a=na = n and b=n1b = n - 1 in the original relation we obtain that f(n)+n1n2+f(n)(n1)f(n) + n - 1 \mid n^{2} + f(n)(n - 1). Since f(n)+n1(n1)(f(n)+n1)f(n) + n - 1 \mid (n - 1)(f(n) + n - 1), then f(n)+n12n1f(n) + n - 1 \mid 2n - 1.

With the substitution a=n1a = n - 1 and b=nb = n in the original relation we obtain that 2n1(n1)2+(n1)f(n)=(n1)(n1+f(n))2n - 1 \mid (n - 1)^{2} + (n - 1)f(n) = (n - 1)(n - 1 + f(n)). Since (2n1,n1)=1(2n - 1, n - 1) = 1, we deduce that 2n1f(n)+n12n - 1 \mid f(n) + n - 1.

Therefore, f(n)+n1=2n1f(n) + n - 1 = 2n - 1, which implies the desired f(n)=nf(n) = n.

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.