2020 AMC 10A Problems/Problem 24
Let be the least positive integer greater than for whichWhat is the sum of the digits of ?
We know that , so we can write . Simplifying, we get . Similarly, we can write , or . Solving these two modular congruences, which we know is the only solution by CRT (Chinese Remainder Theorem used to so,be a system of MODULAR CONGURENCES). Now, since the problem is asking for the least positive integer greater than , we find the least solution is . However, we are have not considered cases where or . so we try . so again we add to . It turns out that does indeed satisfy the original conditions, so our answer is .
Solution 2 (bashing)
We are given that and . This tells us that is divisible by but not . It also tells us that is divisible by 60 but not 120. Starting, we find the least value of which is divisible by which satisfies the conditions for , which is , making . We then now keep on adding until we get a number which satisfies the second equation. This number turns out to be , whose digits add up to .
Solution 3 (bashing but worse)
Assume that has 4 digits. Then , where , , , represent digits of the number (not to get confused with ). As given the problem, and . So we know that (last digit of ). That means that and . We can bash this after this. We just want to find all pairs of numbers such that is a multiple of 7 that is greater than a multiple of . Our equation for would be and our equation for would be , where is any integer. We plug this value in until we get a value of that makes satisfy the original problem statement (remember, ). After bashing for hopefully a couple minutes, we find that works. So which means that the sum of its digits is .
The conditions of the problem reduce to the following. where and where . From these equations, we see that . Solving this diophantine equation gives us that , form. Since, is greater than , we can do some bounding and get that and . Now we start the bash by plugging in numbers that satisfy these conditions. We get , . So the answer is .
Edited by ~fastnfurious1
You can first find that n must be congruent to and . The we can find that and , where x and y are integers. Then we can find that y must be odd, since if it was even the gcd will be 120, not 60. Also, the unit digit of n has to be 7, since the unit digit of 60y is always 0 and the unit digit of 57 is 7. Therefore, you can find that x must end in 1 to satisfy n having a unit digit of 7. Also, you can find that x must not be a multiple of three or else the gcd will be 63. Therefore, you can test values for x and you can find that x=91 satisfies all these conditions.Therefore, n is 1917 and =.-happykeeper
Solution 6 (Reverse Euclidean Algorithm)
We are given that and By applying the Euclidean algorithm, but in reverse, we have and
We now know that must be divisible by and so it is divisible by Therefore, for some integer We know that or else the first condition won't hold ( will be ) and or else the second condition won't hold ( will be ). Since gives us too small of an answer, then so the answer is
tells us . The smallest that satisfies the previous condition and is , so we start from there. If , then . Because , or . We see that , which does not fulfill the requirement for , so we continue by keep on adding to , in order to also fulfill the requirement for . Soon, we see that decreases by every time we add , so we can quickly see that because at that point . Adding up all the digits in , we have .
|2020 AMC 10A (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 10 Problems and Solutions|