2019 AMC 10C Problems/Problem 25
Problem
Let be the least positive integer such that is a multiple of 10000. Find the sum of the digits of . (Note: denotes the greatest integer less than or equal to . )
Solution
We have so we want to solve and .
Solving modulo 16 is fairly simple; the solutions are (or more compactly, ).
To solve modulo 625, observe that at most one of , , and can be divisible by 5. The case gives . The case gives no solutions as by FLT. Thus we want to solve .
Note that implies . As is a solution iff is a solution, we can assume w.l.o.g. that . Then , and plugging in gives .
Taking the LHS mod 5 again, we see , so , so we may let . Using the same method, we have . The solution is , so . Thus the solutions are .
So the solutions mod 16 and 625 are , and . By CRT, each combination gives us a solution mod 10000. Observing that immediately gives us the minimum solution, so and .