2020 AMC 10A Problems/Problem 24

Problem

Let $n$ be the least positive integer greater than $1000$ for which $\gcd(63, n+120) =21\quad \text{and} \quad \gcd(n+63, 120)=60.$ What is the sum of the digits of $n$ ?

$\textbf{(A) } 12 \qquad\textbf{(B) } 15 \qquad\textbf{(C) } 18 \qquad\textbf{(D) } 21\qquad\textbf{(E) } 24$

Solution 1

We know that $(n+57,63)=21, (n-57, 120)= 60$ . Hence, $n+57=21\alpha,n-57=60 \gamma, (\alpha,3)=1, (\gamma,2)=1$ . Subtracting the $2$ equations, $38=7\alpha-20\gamma$ . Letting $\gamma = 2s+1$ , $58=7\alpha-40s$ . Taking $\mod{40}, we have$ \alpha \equiv{14} \pmod{40} $. We are given$ n=21\alpha -57 >1000 \implies \alpha \geq 51 $. Notice that if$ \alpha =54 $then the condition$ (\alpha,3)=1 $is violated. The next possible value of$ \alpha = 94 $satisfies the given condition, giving us the answer$ \boxed{1917} $. Alternatively, we could have said$ \alpha = 40k+14 \equiv{0} \pmod{3} $for$ k \equiv{1} \pmod{3} $only, so$ k \equiv{0,2} \pmod{3}$, giving us our answer.

~Prabh1512

== Solution 2==

We know that$ (Error compiling LaTeX. Unknown error_msg)gcd(63, n+120)=21 $, so we can write$ n+120\equiv0\pmod {21} $. Simplifying, we get$ n\equiv6\pmod {21} $. Similarly, we can write$ n+63\equiv0\pmod {60} $, or$ n\equiv-3\pmod {60} $. Solving these two modular congruences,$ n\equiv237\pmod {420} $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$ 1000 $, we find the least solution is$ n=1077 $. However, we are have not considered cases where$ gcd(63, n+120) =63 $or$ gcd(n+63, 120) =120 $.$ {1077+120}\equiv0\pmod {63} $so we try$ n=1077+420=1497 $.$ {1497+63}\equiv0\pmod {120} $so again we add$ 420 $to$ n $. It turns out that$ n=1497+420=1917 $does indeed satisfy the original conditions, so our answer is$ 1+9+1+7=\boxed{\textbf{(C) }18}$.

==Solution 3 (bashing)==

We are given that$ (Error compiling LaTeX. Unknown error_msg)\gcd(63, n+120)=21 $and$ \gcd(n+63,120) = 60 $. This tells us that$ n+120 $is divisible by$ 21 $but not$ 63 $. It also tells us that$ n+63 $is divisible by 60 but not 120. Starting, we find the least value of$ n+120 $which is divisible by$ 21 $which satisfies the conditions for$ n $, which is$ 1134 $, making$ n=1014 $. We then now keep on adding$ 21 $until we get a number which satisfies the second equation. This number turns out to be$ 1917 $, whose digits add up to$ \boxed{\textbf{(C) } 18}$.

-Midnight

==Solution 4 (bashing but worse)==

Assume that$ (Error compiling LaTeX. Unknown error_msg)n $has 4 digits. Then$ n = abcd $, where$ a $,$ b $,$ c $,$ d $represent digits of the number (not to get confused with$ a * b * c * d $). As given the problem,$ gcd(63, n + 120) = 21 $and$ gcd(n + 63, 120) = 60 $. So we know that$ d = 7 $(last digit of$ n $). That means that$ 12 + abc \equiv0\pmod {7} $and$ 7 + abc\equiv0\pmod {6} $. We can bash this after this. We just want to find all pairs of numbers$ (x, y) $such that$ x $is a multiple of 7 that is$ 5 $greater than a multiple of$ 6 $. Our equation for$ 12 + abc $would be$ 42*j + 35 = x $and our equation for$ 7 + abc $would be$ 42*j + 30 = y $, where$ j $is any integer. We plug this value in until we get a value of$ abc $that makes$ n = abc7 $satisfy the original problem statement (remember,$ abc > 100 $). After bashing for hopefully a couple minutes, we find that$ abc = 191 $works. So$ n = 1917 $which means that the sum of its digits is$ \boxed{\textbf{(C) } 18}$.

~ Baolan

==Solution 5== The conditions of the problem reduce to the following.$ (Error compiling LaTeX. Unknown error_msg)n+120 = 21k $where$ gcd(k,3) = 1 $and$ n+63 = 60l $where$ gcd(l,2) = 1 $. From these equations, we see that$ 21k - 60l = 57 $. Solving this diophantine equation gives us that$ k = 20a + 17 $,$ l = 7a + 5 $form. Since,$ n $is greater than$ 1000 $, we can do some bounding and get that$ k > 53 $and$ l > 17 $. Now we start the bash by plugging in numbers that satisfy these conditions. We get$ l = 33 $,$ k = 97 $. So the answer is$ 1917 \implies 1+9+1+7= \boxed{\textbf{(C) } 18}$.

Edited by ~fastnfurious1

==Solution 6== You can first find that n must be congruent to$ (Error compiling LaTeX. Unknown error_msg)6\equiv0\pmod {21} $and$ 57\equiv0\pmod {60} $. The we can find that$ n=21x+6 $and$ n=60y+57 $, 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$ 1+9+1+7 = \boxed{\textbf{(C) } 18}$.-happykeeper

==Solution 7 (Reverse Euclidean Algorithm)== We are given that$ (Error compiling LaTeX. Unknown error_msg)\gcd(63, n+120) =21 $and$ \gcd(n+63, 120)=60.$By applying the Euclidean algorithm, but in reverse, we have <cmath>\gcd(63, n+120) = \gcd(63, n+120 + 63) = \gcd(63, n+183) = 21</cmath> and <cmath>\gcd(n+63, 120) = \gcd(n+63 + 120, 120) = \gcd(n+183, 120) = 60.</cmath>

We now know that$ (Error compiling LaTeX. Unknown error_msg)n+183 $must be divisible by$ 21 $and$ 60, $so it is divisible by$ \text{lcm}(21, 60) = 420. $Therefore,$ n+183 = 420k $for some integer$ k. $We know that$ 3 \nmid k, $or else the first condition won't hold ($ \gcd $will be$ 63 $) and$ 2 \nmid k, $or else the second condition won't hold ($ \gcd $will be$ 120 $). Since$ k = 1 $gives us too small of an answer, then$ k=5 \implies n = 1917, $so the answer is$ 1+9+1+7 = \boxed{\textbf{(C) } 18}. $==Solution 8==$ \gcd(n+63,120)=60 $tells us$ n+63\equiv60\pmod {120} $. The smallest$ n+63 $that satisfies the previous condition and$ n>1000 $is$ 1140 $, so we start from there. If$ n+63=1140 $, then$ n+120=1197 $. Because$ \gcd(n+120,63)=21 $,$ n+120\equiv21\pmod {63} $or$ n+120\equiv42\pmod {63} $. We see that$ 1197\equiv0\pmod {63} $, which does not fulfill the requirement for$ n+120 $, so we continue by keep on adding$ 120 $to$ 1197 $, in order to also fulfill the requirement for$ n+63 $. Soon, we see that$ n+120\pmod {63} $decreases by$ 6 $every time we add$ 120 $, so we can quickly see that$ n=1917 $because at that point$ n+120\equiv21\pmod {63} $. Adding up all the digits in$ 1917 $, we have$ \boxed{\textbf{(C) } 18}$.

-SmileKat32

==Solution 9== We are able to set-up the following system-of-congruences: <cmath>n \equiv 6 \pmod {21},</cmath> <cmath>n \equiv 57 \pmod {60}.</cmath> Therefore, by definition, we are able to set-up the following system of equations: <cmath>n = 21a + 6,</cmath> <cmath>n = 60b + 57.</cmath> Thus, <cmath>21a + 6 = 60b + 57</cmath> <cmath>\implies 7a + 2 = 20b + 19.</cmath> We know$ (Error compiling LaTeX. Unknown error_msg)7a \equiv 0 \pmod {7}, $and since$ 7a = 20b + 17, $therefore$ 20b + 17 \equiv 0 \pmod{7}. $Simplifying this congruence further, we have <cmath>5b \equiv 1 \pmod{7}</cmath> <cmath>\implies b \equiv 3 \pmod {7}.</cmath> Thus, by definition,$ b = 7x + 3. $Substituting this back into our original equation, <cmath>n = 60(7x + 3) + 57</cmath> <cmath>\implies n = 420x + 180 + 57</cmath> <cmath>\implies n = 420x + 237.</cmath> By definition, we are able to set-up the following congruence: <cmath>n \equiv 237 \pmod{420}.</cmath> Thus,$ n = 1917 $, so our answer is simply$ \boxed{18}$.

(Remarks.$ (Error compiling LaTeX. Unknown error_msg)n \equiv 6 \pmod{21} $since$ n \equiv -120 \pmod{21},$by definition &$ (Error compiling LaTeX. Unknown error_msg)n \equiv 57 \pmod{60} $since$ n \equiv -63 \pmod{60},$by definition.

Remember,$ (Error compiling LaTeX. Unknown error_msg)5b \equiv 1 \pmod{7} \implies 5b \equiv 15 \pmod{7} \implies b \equiv 3 \pmod{7}. $Lastly, the reason why$ n \neq 1077 $is$ n + 120 $would be divisible by$ 63$, which is not possible due to the certain condition.)

~ nikenissan

== Solution 10==

First, we find$ (Error compiling LaTeX. Unknown error_msg)n $. We know that it is greater than$ 1000 $, so we first input$ n = 1000 $. From the first equation,$ gcd(63, n + 120) = 21 $, we know that if$ n $is correct, after we add$ 120 $to it, it should be divisible by$ 21 $, but not$ 63 $. <cmath>\frac{n + 120}{21}, </cmath> <cmath>\frac{1120}{21}, </cmath> <cmath>53 r 7. </cmath> Uh oh. To get to the nearest number divisible by$ 21 $, we have to add$ 14 $to cancel out the remainder. (Note that we don't subtract$ 7 $to get to$ 53 $;$ n $is already at its lowest possible value!) Adding$ 14 $to$ 1000 $gives us$ n = 1014 $. (Note:$ n$is currently divisible by 63, but that's fine since we'll be changing it in the next step.)

Now using, the second equation,$ (Error compiling LaTeX. Unknown error_msg)gcd(n + 63, 120) = 60 $, we know that if$ n $is correct, after we add$ 63 $to it, it should be divisible by$ 60 $, but not$ 120 $. <cmath>\frac{n + 63}{60}, </cmath> <cmath>\frac{1077}{60}, </cmath> <cmath>17r57. </cmath> Uh oh (again). This requires some guessing and checking. We can add$ 21 $over and over again until$ n $is valid. This changes$ n $while also maintaining that$ \frac{n + 120}{21} $has no remainders. After adding$ 21 $once, we get$ 18 r 18 $. By pure luck, adding$ 21 $two more times gives us$ 19 $with no remainders. We now have$ 1077 + 21 + 21 + 21 = 1140 $. However, this number is divisible by$ 120 $. To get the next possible number, we add the LCM of$ 21 $and$ 60 $(once again, to maintain divisibility), which is$ 420 $. Unfortunately,$ 1140 + 420 = 1560 $is still divisible by$ 120 $. Adding$ 420 $again gives us$ 1980 $, which is valid. However, remember that this is equal to$ n + 63 $, so subtracting$ 63 $from$ 1980 $gives us$ 1917 $, which is$ n$.

The sum of its digits are$ (Error compiling LaTeX. Unknown error_msg)1 + 9 + 1 + 7 = 18$.

So, our answer is$ (Error compiling LaTeX. Unknown error_msg)\boxed{\textbf{(C) }18}$. ~ primegn

Video Solution 1

https://youtu.be/tk3yOGG2K-s ~ Richard Rusczyk

Video Solution 2

Education The Study of Everything

https://youtu.be/e5BJKMEIPEM

Video Solution 3

https://www.youtube.com/watch?v=gdGmSyzR908&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=5 ~ MathEx

2020 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 23	Followed by Problem 25
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

Page

Toolbox

Search