Find all real-valued functions on the positive integers such that for all integer , and for all integers .
Solution
The condition allows to make all computations modulo , which is a prime number. Hence the problem asks the number of multiplicative functions in .
Two such functions are and . From now on suppose is different from these two functions.
Substituting , ; substituting , . By Euler-Fermat's theorem, so .
Now let be a primitive root of (that is, such that the least positive integer such that is ). So every in can be written as for some . Then . If then if divides and otherwise; if then if divides , if is a quadratic residue modulo (such residues are ) and otherwise.
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.