Browse · MathNet
PrintBMO Short List
number theory
Problem
Given an integer , determine all functions from the positive integers into themselves such that is divisible by for all positive integers . Albania
Solution
The identity is the only function satisfying the condition in the statement. Begin by letting the 's be all equal to to infer that is divisible by , so for all positive integers .
Claim. for all but finitely many primes .
Assume the Claim for the moment to proceed as follows: Fix any positive integer , and let be a large enough prime, e.g., . Then let one of the 's be equal to and the remaining be all equal to , and use the Claim to infer that the number is divisible by , and hence so is . Since is large enough, this forces , and since , it follows that , as desired.
Proof of the Claim. If is even, let , and let half of the 's be all equal to and the other half be all equal to , to infer that is divisible by . By Wilson's theorem, the latter is divisible by , and hence so is the former. Since , the number is not divisible by , so is not divisible by either, forcing . Recall now that , to conclude that .
If is odd, let , let of the 's be all equal to , let one of the 's be equal to , and let the remaining ones (if any) be all equal to , to infer that is divisible by . By Wilson's theorem, the latter is divisible by , and hence so is the former. Since , the number is not divisible by , so is not divisible by either, forcing . Recall again that , to conclude that .
Claim. for all but finitely many primes .
Assume the Claim for the moment to proceed as follows: Fix any positive integer , and let be a large enough prime, e.g., . Then let one of the 's be equal to and the remaining be all equal to , and use the Claim to infer that the number is divisible by , and hence so is . Since is large enough, this forces , and since , it follows that , as desired.
Proof of the Claim. If is even, let , and let half of the 's be all equal to and the other half be all equal to , to infer that is divisible by . By Wilson's theorem, the latter is divisible by , and hence so is the former. Since , the number is not divisible by , so is not divisible by either, forcing . Recall now that , to conclude that .
If is odd, let , let of the 's be all equal to , let one of the 's be equal to , and let the remaining ones (if any) be all equal to , to infer that is divisible by . By Wilson's theorem, the latter is divisible by , and hence so is the former. Since , the number is not divisible by , so is not divisible by either, forcing . Recall again that , to conclude that .
Final answer
f(n) = n for all positive integers n
Techniques
Fermat / Euler / Wilson theoremsPrime numbers