Problem:
Find the least positive integer n for which 2n+5nβn is a multiple of 1000.
Solution:
Notice that
2n+5nβnβ‘0mod1000
means that
2n+5nβ‘0mod8
and
2n+5nβ‘0mod125
Let's start with mod 8, and notice that nβ₯3 so it makes the conditions a little bit easier to handle.
If 5nβ‘nmod8, we can just try different numbers to see that the only one that satisfies this congruence is nβ‘5mod8.
From here,
2nβ‘nmod125 is a little bit more challenging to evaluate.
Notice that 2nβ‘nmod125β2nβ‘nmod5.
To evluate this, we see that out of the possible Ο(125)=100 powers to try, 21,22,....,2100, that we can bash, noticing that 2n is even, so its residue mod 5 will be odd, and n has to be odd from nβ‘5mod8.
Thus, there's only 5100β=20 to try, half of which can be eliminated because n is odd,
and this yields that nβ‘3mod20 and nβ‘17mod20.
Notice when expanding this, to mod 25, that we have n mod 20 and that 220β‘1mod25.
The right hand side repeats every 25 (we are taking mod 25), and the left side repeats every 20, and so we have to test values mod 100, that are nβ‘3,17mod20.
Trying 3,23,43,63,83 we'd need
2nβ‘nβ‘23β‘8mod25, which works when nβ‘83mod100
Similarly, for nβ‘17mod20, we'd have nβ‘97mod100.
Calculating these mod125, we'd have that 297β‘47mod125 and 283β‘33mod125.
When looking at it mod 125, notice how the left side repeats mod Ο(125)=100 and the right side repeats mod 125, so we have to look at it mod 500, where we'd get a valid solution at
nβ‘283mod500 and nβ‘297mod500
Combining these with the conditions we got off the first equation with 5nβ‘nmod8, we'd have that 797 works so the answer is 797β.
The problems on this page are the property of the MAA's American Mathematics Competitions