Competition problem — Number theory

Library / /43 of 87

Number theory Difficulty 5.7 AIME, harder Prove it Austria

Determine all functions $f$ mapping the integers to the integers with the following property: For any two (not necessarily different) numbers $m$ and $n$ , $\text{gcd}(m, n)$ is a divisor of $f(m) + f(n)$ . (Note that $\text{gcd}(m, n) = \text{gcd}(|m|, |n|)$ and $\text{gcd}(m, 0) = |m|$ holds for all integers $m$ and $n$ .)

Solution

If $t$ is an odd number and we set $m = n = t$ , we see that $t|2f(t)$ must hold, which means that $t|f(t)$ must hold for all odd values of $t$ .

If we now set $m = 0$ and $n = t$ (with $t$ still odd), we further see that $t|f(0) + f(t)$ must also hold, which means that $f(0)$ must be divisible by all odd numbers, which is only possible for $f(0) = 0$ .

Next, we set $m = 0$ and $n = s$ with $s$ even, and in this case we also obtain $s|f(0) + f(s) = f(s)$ .

It follows that $n|f(n)$ must hold for all integers $n$ , and it is obvious that any function with this property also fulfills the requirements of the problem, which completes the solution. $\square$

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.