Determine all positive integers such that there exist positive integers and which satisfy
Here denotes the sum of digits of . (Romania 1999)
Solution
Notice that, for each positive integer , the numbers and give the same remainder when divided by .
Applying this observation to , we conclude that , and give the same remainder when divided by . This implies that and are both divisible by . But then and are also divisible by . This proves that any positive integer satisfying the given condition must be divisible by .
Let us now prove the converse: let be a multiple of , i.e. let for some positive integer . Taking numbers
where each of the numbers has exactly digits, we obtain a pair which satisfies .
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.