Let be a prime. Determine all positive integers for which the following condition is satisfied for all the integers :
Condition: If is divisible by , then it is also divisible by .
Solution
If, for a pair of integers and a positive integer , is divisible by , we write .
We will show that the numbers we seek are those of the form , where is a positive integer.
Let us first show that if satisfies the condition of the problem, then must be a multiple of . To see this let . Then from , we get the fact that is divisible by , and hence by the condition of the problem, is divisible by as well. By using the binomial expansion we get , and therefore, . This implies that is a multiple of , and therefore, must be a multiple of .
Conversely, we will show that if for a positive integer , then it satisfies the condition of the problem. First we note that holds by Fermat's Little Theorem. This shows that if is a multiple of , then so is . Now we have
from which we conclude that is a multiple of . Thus, we see that satisfies the condition of the problem.