Maths Olympiad Prep

Library / /131 of 299

Algebra Difficulty 6.4 National Olympiad Prove it Iran

kZ+k \in \mathbb{Z}^+ is a fixed number. Find all functions f:Z+Z+f : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+ such that for infinitely many prime numbers like qq, qkq^k is in the range of ff and also for all m,nZ+m, n \in \mathbb{Z}^+
f(m)+f(n)f(m+n) f(m) + f(n) \mid f(m + n)

Solution

We prove by induction that f(n)=nf(1)f(n) = n f(1).

Let c1,c2,c_1, c_2, \dots, be the sequence of positive integers such that f(ci)=pikf(c_i) = p_i^k. Then one has
f(ci(d+1))+f(d+1)f(ci)=pik f(c_i - (d+1)) + f(d+1) \mid f(c_i) = p_i^k
and hence f(ci(d+1))=pijf(d+1)f(c_i - (d+1)) = p_i^j - f(d+1) for some positive integer jkj \le k. By pigeonhole principle, there are infinitely many ii that gives us the same jj and hence we can assume that jj is fixed since we can just consider that sequence instead. Similarly, one has f(cik)=pijf(k)f(c_i - k) = p_i^{j'} - f(k) for some fixed positive integer jj'. Now we have
f(1)+f(ci(d+1))f(cid)    pijf(d+1)+f(1)pijf(d). f(1) + f(c_i - (d+1)) \mid f(c_i - d) \implies p_i^j - f(d+1) + f(1) \mid p_i^{j'} - f(d).
Let j=aj+bj' = a j + b where 0b<j0 \le b < j. Then our divisibility condition becomes
pijf(d+1)+f(1)(f(d+1)f(1))apibf(d) p_i^j - f(d+1) + f(1) \mid (f(d+1) - f(1))^a p_i^b - f(d)
but since b<jb < j and a<ka < k, the RHS is less than the LHS when pip_i is large enough which is a contradiction unless the LHS equals zero. In which case one has
(f(d+1)f(1))apib=f(d) (f(d+1) - f(1))^a p_i^b = f(d)
and so b=0b = 0, giving us (f(d+1)f(1))a=f(d)(f(d+1) - f(1))^a = f(d). On the other hand, one also has
f(1)+f(d)f(d+1) f(1) + f(d) \mid f(d+1)
giving us
(f(d+1)f(1))a+f(1)f(d+1). (f(d+1) - f(1))^a + f(1) \mid f(d+1).
Letting f(d+1)f(1)=cf(d+1) - f(1) = c, one has
ca+f(1)c+f(1) c^a + f(1) \mid c + f(1)
which is impossible unless ca=cc^a = c, in which case either c=1c = 1 or a=1a = 1. If c=1c = 1, then f(d)=1f(d) = 1 and f(1)+f(d1)f(d)f(1) + f(d-1) \mid f(d) is impossible. Thus it must be that a=1a = 1 which gives us f(d+1)=f(d)+f(1)f(d+1) = f(d) + f(1). By induction, f(n)=nf(1)f(n) = n f(1) as desired.

Now clearly any function satisfying f(n)=nf(1)f(n) = n f(1) satisfies the second condition. For the first condition, it is clear that one must have f(1)=1f(1) = 1. Hence the only solution is f(n)=nf(n) = n for all nZ+n \in \mathbb{Z}^+.

f(n)=n\boxed{f(n) = n} for all nZ+n \in \mathbb{Z}^+.

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.