Problem:
Find the least positive integer n for which 2n+5nβn is a multiple of 1000.
Solution:
Answer (797):
By the Chinese Remainder Theorem, the required condition is equivalent to
nβ‘2n+5n(mod8) and nβ‘2n+5n(mod125)
Because n=1 and n=2 do not satisfy the conditions, it follows that nβ₯3, in which case these congruences reduce to nβ‘5n(mod8) and nβ‘2n(mod125).
The congruence nβ‘5n(mod8) implies that nβ‘5nβ‘1(mod2), so n is odd. Because 52β‘1(mod8), it follows that nβ‘5nβ‘51β‘5(mod8).
The congruence nβ‘2n(mod125) implies that nβ‘2n(mod5). It is known that nβ‘5(mod8), which implies that nβ‘1(mod4). Then by Fermat's Little Theorem, nβ‘2nβ‘21β‘2(mod5). Next, the original congruence nβ‘2n(mod125) also implies that nβ‘2n(mod25).
Together, nβ‘1(mod4) and nβ‘2(mod5) imply that nβ‘β3(mod20), which is the only solution by the Chinese Remainder Theorem.
Because 20=Ο(25), by Euler's Theorem,
nβ‘2nβ‘2β3β‘8β1β‘β3(mod25)
This congruence, together with nβ‘1(mod4), implies nβ‘β3(mod100). By Euler's Theorem,
nβ‘2nβ‘2β3β‘8β1β‘47(mod125)
Finally, the above with nβ‘5(mod8) implies that nβ‘797(mod1000).
To see that nβ‘797(mod1000) indeed implies nβ‘2n+5n(mod1000), note that every positive integer n with nβ‘797(mod1000) satisfies all the congruences nβ‘1(mod2),nβ‘5(mod8),nβ‘β3(mod100), and nβ‘2β3(mod125). This can be confirmed directly; but it can also be seen without computation by appealing to the argument above, in which the residue 797 (mod 1000) was constructed by repeatedly applying the Chinese Remainder Theorem with these four congruences. Then
5nβ‘51β‘5β‘n(mod8) and 2nβ‘2β3β‘n(mod125)
by Euler's Theorem, as needed. Thus 797 is the requested value of n.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions