Find all functions such that for all positive integers with ,
Here denotes the number of positive integers coprime to and not exceeding .
Solution
Let be a function such that for all positive integers and with , the following holds:
where denotes the Euler's totient function, which counts the number of positive integers up to that are coprime to .
We start by examining the implications of the given functional equation for specific values of .
1. **Case :**
2. **Case :**
Since , it follows that .
3. **Case :**
4. **Case :**
Since , it follows that .
By induction, we can generalize that for any prime and positive integer :
Using this pattern, we assume for some constant . We verify this by substituting back into the original functional equation:
Thus, the function that satisfies the given condition is:
The answer is: = km for any positive integer constant } k.}
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.