Problem:
How many positive integer multiples of 1001 can be expressed in the form 10j−10i, where i and j are integers and 0≤i<j≤99?
Solution:
Because
10j−10i=10i(10j−i−1)
and 1001=7⋅11⋅13 is relatively prime to 10i, it is necessary to find i and j so that 10j−i−1 is divisible by the primes 7,11, and 13. Notice that 106 is the smallest power of 10 that leaves a remainder of 1 when divided by 7 or 13, and that 102 is the smallest power of 10 that leaves a remainder of 1 when divided by 11. Hence 10i(10j−i−1) is divisible by 1001 if and only if j−i=6n for some positive integer n. Thus it is necessary to count the number of integer solutions to
i+6n=j, where j≤99,i≥0,n>0
For each n=1,2,3,…,16, there are 100−6n suitable values of i (and j), so the number of solutions is
94+88+82+⋯+4=784​
The problems on this page are the property of the MAA's American Mathematics Competitions