Problem:
Find all functions (where is the set of positive integers) such that ! for all positive integers and such that divides for all distinct positive integers .
Solution:
There are three solutions: the constant functions 1,2 and the identity function. Let us prove that these are the only ones. Consider such a function and suppose first of all that there exists such that . Then are all fixed points of . So there is an increasing sequence of fixed points. If is any positive integer, divides for all , and so it also divides for all . Thus and since it holds for any , we are done in this case.
Now suppose that has no fixed points greater than 2 . Let be a prime and observe that by Wilson's theorem), thus is a multiple of . Clearly is 1 or 2 . As , the fact that divides implies that . Since is not a multiple of (again by Wilson), we deduce that actually . On the other hand, divides . Thus either or . As , the last case is excluded and so and this for all primes . Taking any positive integer, we deduce that divides and this holds for all large primes . Thus and is constant. The conclusion is now clear.
This problem and solution were suggested by Gabriel Dospinescu.
The problems on this page are the property of the MAA's American Mathematics Competitions