Skip to main content
OlympiadHQ

Browse · MathNet

Print

BMO 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 .
Final answer
f(n) = n for all positive integers n

Techniques

Fermat / Euler / Wilson theoremsPrime numbers