Let be the set of all positive rational numbers. Find all functions satisfying and
for all positive integers and .
Solution
First, for a pair of positive integers (where ), define one operation on it as replacing the larger number with the remainder obtained by dividing it by the smaller number. (For example becomes , becomes )
Let be such that for every positive rational number (where are coprime positive integers), the following holds:
after performing the operation on the pair a total of times, one of the two numbers becomes 1 and the other is not 0.
First, since are coprime, exists for every positive rational number. Moreover, once one of them becomes 1, the next operation will make the other one become 0, and after that no further operation can be performed, so is unique. Hence is well-defined.
Next, it is not hard to see that . And when ,
Here is a positive integer.
Next, we prove by mathematical induction that , where are coprime positive integers. We induct on .
If , then or .
If , substituting into the original equation gives
If , substituting into the original equation and combining with (2) gives .
Thus the statement holds when .
Suppose the statement holds when ; then when , we discuss two cases.
Case (1): . Let , then by (1) we know . Substituting into the original equation and combining with (1) and the induction hypothesis, we get
Case (2): . Since , by (1) we know .
Also , so by (3) we know ,
Substituting into the original equation gives .
Combining the above, the statement holds when . Hence by mathematical induction the statement always holds.
Therefore, , where are any coprime positive integers.