Problem:
Let N be the greatest four-digit positive integer with the property that whenever one of its digits is changed to 1, the resulting number is divisible by 7. Let Q and R be the quotient and the remainder, respectively, when N is divided by 1000. Find Q+R.
Solution:
Let N=a b c d, where a,b,c, and d are digits and a≥1. Then the given condition is equivalent to
1000+100b+10c+d1000a+100+10c+d1000a+100b+10+d1000a+100b+10c+1≡0mod7≡0mod7≡0mod7≡0mod7.
Adding these four congruences gives 3N+1111≡0mod7, from which N≡3mod7. Therefore
1000a+100b+10c+d≡3mod7.
Subtracting each of the four previous congruences from this new congruence gives
1000(a−1)100(b−1)10(c−1)d−1≡3mod7≡3mod7≡3mod7≡3mod7,
from which a=5,b=6,c=2 or 9, and d=4. The required number is N=5694. The requested sum is 5+694=699.
The problems on this page are the property of the MAA's American Mathematics Competitions