Denote by the set of all positive integers. Find all functions that satisfy the following conditions:
* holds for all positive integers and .
* If any number among and is divisible by prime number , then is divisible by as well. (Ivan Krijan)
Solution
Plugging into the first given condition, we get .
On the other hand, by plugging we get
Using the first given condition in its original form, it follows that
Let be a fixed prime number such that , meaning that . Since , we also have . Therefore, and
for all positive integers and , and primes such that .
Note that the right-hand side in does not depend on , hence fixing and varying would yield infinitely many odd prime divisors of , which is possible only if the latter equals 0, i.e.
for every positive integer .
Therefore, , , i.e. (by mathematical induction).
In a similar fashion, starting with , we infer that .
Finally, from
it follows that . This function clearly satisfies the second given condition, hence it is the only solution.
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.