Difference between revisions of "2020 AMC 10A Problems/Problem 24"
MRENTHUSIASM (talk | contribs) m (Use \ldots instead of \cdots for lists.) |
|||
(44 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math>n</math> be the least positive integer greater than <math>1000</math> for which<cmath>\gcd(63, n+120) =21\quad \text{and} \quad \gcd(n+63, 120)=60.</cmath>What is the sum of the digits of <math>n</math>? | + | Let <math>n</math> be the least positive integer greater than <math>1000</math> for which |
+ | |||
+ | <cmath>\gcd(63, n+120) =21\quad \text{and} \quad \gcd(n+63, 120)=60.</cmath> | ||
+ | |||
+ | What is the sum of the digits of <math>n</math>? | ||
<math>\textbf{(A) } 12 \qquad\textbf{(B) } 15 \qquad\textbf{(C) } 18 \qquad\textbf{(D) } 21\qquad\textbf{(E) } 24</math> | <math>\textbf{(A) } 12 \qquad\textbf{(B) } 15 \qquad\textbf{(C) } 18 \qquad\textbf{(D) } 21\qquad\textbf{(E) } 24</math> | ||
== Solution 1 == | == Solution 1 == | ||
− | We know that <math>(n+57,63)=21, (n-57, 120)= 60</math>. Hence, <math>n+57=21\alpha,n-57=60 \gamma, (\alpha,3)=1, (\gamma,2)=1</math>. Subtracting the <math>2</math> equations, <math>38=7\alpha-20\gamma</math>. Letting <math>\gamma = 2s+1</math>, <math>58=7\alpha-40s</math>. Taking <math>\mod{40}</math>, we have <math>\alpha \equiv{14} \pmod{40}</math>. We are given <math>n=21\alpha -57 >1000 \implies \alpha \geq 51</math>. Notice that if <math>\alpha =54</math> then the condition <math>(\alpha,3)=1</math> is violated. The next possible value of <math>\alpha = 94</math> satisfies the given condition, giving us the answer <math>\boxed{1917}</math>. Alternatively, we could have said <math>\alpha = 40k+14 \equiv{0} \pmod{3}</math> for <math>k \equiv{1} \pmod{3}</math> only, so <math>k \equiv{0,2} \pmod{3}</math>, giving us our answer. | + | We know that <math>(n+57,63)=21, (n-57, 120)= 60</math> by the Euclidean Algorithm. Hence, let <math>n+57=21\alpha, n-57=60 \gamma, (\alpha,3)=1, (\gamma,2)=1</math>. Subtracting the <math>2</math> equations, <math>38=7\alpha-20\gamma</math>. Letting <math>\gamma = 2s+1</math>, <math>58=7\alpha-40s</math>. Taking <math>\mod{40}</math>, we have <math>\alpha \equiv{14} \pmod{40}</math>. We are given <math>n=21\alpha -57 >1000 \implies \alpha \geq 51</math>. Notice that if <math>\alpha =54</math> then the condition <math>(\alpha,3)=1</math> is violated. The next possible value of <math>\alpha = 94</math> satisfies the given condition, giving us the answer <math>\boxed{1917}</math>. Alternatively, we could have said <math>\alpha = 40k+14 \equiv{0} \pmod{3}</math> for <math>k \equiv{1} \pmod{3}</math> only, so <math>k \equiv{0,2} \pmod{3}</math>, giving us our answer. Since the problem asks for the sum of the digits of <math>n</math>, <math>1+9+1+7</math> = <math>18</math> or <math>\boxed{\textbf{(C) } 18}</math> is our answer. |
+ | ~Prabh1512, with edits by Terribleteeth. | ||
− | + | == Solution 2== | |
+ | We know that <math>\text{gcd}(63, n+120)=21</math>, so we can write <math>n+120\equiv0\pmod {21}</math>. Simplifying, we get <math>n\equiv6\pmod {21}</math>. Similarly, we can write <math>n+63\equiv0\pmod {60}</math>, or <math>n\equiv-3\pmod {60}</math>. Solving these two modular congruences, <math>n\equiv237\pmod {420}</math> which we know is the only solution by the Chinese Remainder Theorem. Now, since the problem is asking for the least positive integer greater than <math>1000</math>, we find the least solution is <math>n=1077</math>. | ||
− | == | + | However, we have not considered cases where <math>\text{gcd}(63, n+120)=63</math> or <math>\text{gcd}(n+63, 120)=120</math>. |
− | + | <math>{1077+120} \equiv 0 \pmod {63}</math> so we try <math>n=1077+420=1497</math>. <math>{1497+63}\equiv0\pmod {120}</math> so again we add <math>420</math> to <math>n</math>. It turns out that <math>n=1497+420=1917</math> does indeed satisfy the original conditions, so our answer is <math>1+9+1+7=\boxed{\textbf{(C) }18}</math>. | |
− | |||
− | |||
+ | ==Solution 3 (Bashing)== | ||
We are given that <math>\gcd(63, n+120)=21</math> and <math>\gcd(n+63,120) = 60</math>. This tells us that <math>n+120</math> is divisible by <math>21</math> but not <math>63</math>. It also tells us that <math>n+63</math> is divisible by 60 but not 120. Starting, we find the least value of <math>n+120</math> which is divisible by <math>21</math> which satisfies the conditions for <math>n</math>, which is <math>1134</math>, making <math>n=1014</math>. We then now keep on adding <math>21</math> until we get a number which satisfies the second equation. This number turns out to be <math>1917</math>, whose digits add up to <math>\boxed{\textbf{(C) } 18}</math>. | We are given that <math>\gcd(63, n+120)=21</math> and <math>\gcd(n+63,120) = 60</math>. This tells us that <math>n+120</math> is divisible by <math>21</math> but not <math>63</math>. It also tells us that <math>n+63</math> is divisible by 60 but not 120. Starting, we find the least value of <math>n+120</math> which is divisible by <math>21</math> which satisfies the conditions for <math>n</math>, which is <math>1134</math>, making <math>n=1014</math>. We then now keep on adding <math>21</math> until we get a number which satisfies the second equation. This number turns out to be <math>1917</math>, whose digits add up to <math>\boxed{\textbf{(C) } 18}</math>. | ||
-Midnight | -Midnight | ||
− | ==Solution 4 ( | + | ==Solution 4 (Bashing but Worse)== |
− | |||
Assume that <math>n</math> has 4 digits. Then <math>n = abcd</math>, where <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> represent digits of the number (not to get confused with <math>a * b * c * d</math>). As given the problem, <math>gcd(63, n + 120) = 21</math> and <math>gcd(n + 63, 120) = 60</math>. So we know that <math>d = 7</math> (last digit of <math>n</math>). That means that <math>12 + abc \equiv0\pmod {7}</math> and <math>7 + abc\equiv0\pmod {6}</math>. We can bash this after this. We just want to find all pairs of numbers <math>(x, y)</math> such that <math>x</math> is a multiple of 7 that is <math>5</math> greater than a multiple of <math>6</math>. Our equation for <math>12 + abc</math> would be <math>42*j + 35 = x</math> and our equation for <math>7 + abc</math> would be <math> 42*j + 30 = y</math>, where <math>j</math> is any integer. We plug this value in until we get a value of <math>abc</math> that makes <math>n = abc7</math> satisfy the original problem statement (remember, <math>abc > 100</math>). After bashing for hopefully a couple minutes, we find that <math>abc = 191</math> works. So <math>n = 1917</math> which means that the sum of its digits is <math>\boxed{\textbf{(C) } 18}</math>. | Assume that <math>n</math> has 4 digits. Then <math>n = abcd</math>, where <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> represent digits of the number (not to get confused with <math>a * b * c * d</math>). As given the problem, <math>gcd(63, n + 120) = 21</math> and <math>gcd(n + 63, 120) = 60</math>. So we know that <math>d = 7</math> (last digit of <math>n</math>). That means that <math>12 + abc \equiv0\pmod {7}</math> and <math>7 + abc\equiv0\pmod {6}</math>. We can bash this after this. We just want to find all pairs of numbers <math>(x, y)</math> such that <math>x</math> is a multiple of 7 that is <math>5</math> greater than a multiple of <math>6</math>. Our equation for <math>12 + abc</math> would be <math>42*j + 35 = x</math> and our equation for <math>7 + abc</math> would be <math> 42*j + 30 = y</math>, where <math>j</math> is any integer. We plug this value in until we get a value of <math>abc</math> that makes <math>n = abc7</math> satisfy the original problem statement (remember, <math>abc > 100</math>). After bashing for hopefully a couple minutes, we find that <math>abc = 191</math> works. So <math>n = 1917</math> which means that the sum of its digits is <math>\boxed{\textbf{(C) } 18}</math>. | ||
Line 29: | Line 33: | ||
==Solution 5== | ==Solution 5== | ||
− | The conditions of the problem reduce to the following. <math>n+120 = 21k</math> where <math>gcd(k,3) = 1</math> and <math>n+63 = 60l</math> where <math>gcd(l,2) = 1</math>. From these equations, we see that <math>21k - 60l = 57</math>. Solving this | + | The conditions of the problem reduce to the following. <math>n+120 = 21k</math> where <math>gcd(k,3) = 1</math> and <math>n+63 = 60l</math> where <math>gcd(l,2) = 1</math>. From these equations, we see that <math>21k - 60l = 57</math>. Solving this Diophantine equation gives us that <math>k = 20a + 17</math>, <math>l = 7a + 5</math> form. Since, <math>n</math> is greater than <math>1000</math>, we can do some bounding and get that <math>k > 53</math> and <math>l > 17</math>. Now we start the bash by plugging in numbers that satisfy these conditions. <math>a=4</math> is the first number that works so we get <math>l = 33</math>, <math>k = 97</math>. <math>n=21(97)-120=60(33)-63=1917</math>. Our answer is then <math>1+9+1+7=\boxed{\textbf{(C) } 18}</math>. |
− | \boxed{\textbf{(C) } 18}</math>. | ||
− | |||
− | |||
==Solution 6== | ==Solution 6== | ||
Line 97: | Line 98: | ||
So, our answer is <math>\boxed{\textbf{(C) }18}</math>. ~ primegn | So, our answer is <math>\boxed{\textbf{(C) }18}</math>. ~ primegn | ||
− | == | + | ==Solution 11 (Euclidean Algorithm)== |
+ | By the Euclidean Algorithm, we have | ||
+ | <cmath>\begin{alignat*}{8} | ||
+ | \gcd(63,n+120)&=\hspace{1mm}&&\gcd(63,\phantom{ }\underbrace{n+120-63k_1}_{(n+120) \ \mathrm{mod} \ 63}\phantom{ })&&=21, &&\hspace{10mm}(1) \\ | ||
+ | \gcd(n+63,120)&=&&\gcd(\phantom{ }\underbrace{n+63-120k_2}_{(n+63) \ \mathrm{mod} \ 120}\phantom{ },120)&&=60.&&\hspace{10mm}(2) | ||
+ | \end{alignat*}</cmath> | ||
+ | Clearly, <math>n+120-63k_1</math> must be either <math>21</math> or <math>42,</math> and <math>n+63-120k_2</math> must be <math>60.</math> | ||
+ | |||
+ | More generally, let <math>t\in\{1,2\},</math> so we get | ||
+ | <cmath>\begin{align*} | ||
+ | n+120-63k_1&=21t, &\hspace{55.5mm}(1*) \\ | ||
+ | n+63-120k_2&=60. &\hspace{55.5mm}(2*) | ||
+ | \end{align*}</cmath> | ||
+ | Subtracting <math>(2*)</math> from <math>(1*)</math> and then simplifying give | ||
+ | <cmath>\begin{align*} | ||
+ | 57-63k_1+120k_2&=21t-60 \\ | ||
+ | 117-63k_1+120k_2&=21t \\ | ||
+ | 39-21k_1+40k_2&=7t. \hspace{54mm}(\bigstar) | ||
+ | \end{align*}</cmath> | ||
+ | Taking <math>(\bigstar)</math> modulo <math>7</math> produces | ||
+ | <cmath>\begin{align*} | ||
+ | 4+5k_2&\equiv0\pmod{7} \\ | ||
+ | k_2&\equiv2\pmod{7}. | ||
+ | \end{align*}</cmath> | ||
+ | Recall that <math>n>1000.</math> From <math>(2*),</math> it follows that <cmath>1063-120k_2<n+63-120k_2=60,</cmath> from which <math>k_2>8.</math> Therefore, the possible values for <math>k_2</math> are <math>9,16,23,\ldots.</math> | ||
+ | |||
+ | We need to check whether positive integers <math>k_1</math> and <math>t</math> (where <math>t\in\{1,2\}</math>) exist in <math>(1*):</math> | ||
+ | <ul style="margin-left: 1.5em, list-style-type: square;"> | ||
+ | <li>If <math>k_2=9,</math> then substituting into <math>(2*)</math> gives <math>n=1077.</math> Next, substituting into <math>(1*)</math> produces <math>1197-63k_1=21t,</math> or <math>57-3k_1=t.</math> <p> | ||
+ | There are no solutions <math>(k_1,t).</math></li><p> | ||
+ | <li>If <math>k_2=16,</math> then substituting into <math>(2*)</math> gives <math>n=1917.</math> Next, substituting into <math>(1*)</math> produces <math>2037-63k_1=21t,</math> or <math>97-3k_1=t.</math> <p> | ||
+ | The solution is <math>(k_1,t)=(32,1).</math></li><p> | ||
+ | </ul> | ||
+ | Finally, the least such positive integer <math>n</math> is <math>1917.</math> The sum of its digits is <math>1+9+1+7=\boxed{\textbf{(C) } 18}.</math> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
− | https:// | + | ==Video Solutions== |
+ | ===Video Solution 1 (Richard Rusczyk)=== | ||
+ | https://artofproblemsolving.com/videos/amc/2020amc10a/514 | ||
− | ==Video Solution 2== | + | ===Video Solution 2=== |
− | + | https://youtu.be/8mNMKH0T9W0 - Happytwin | |
+ | ===Video Solution 3 (Quick & Simple)=== | ||
https://youtu.be/e5BJKMEIPEM | https://youtu.be/e5BJKMEIPEM | ||
− | == Video Solution | + | Education The Study of Everything |
+ | |||
+ | ===Video Solution 4=== | ||
https://www.youtube.com/watch?v=gdGmSyzR908&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=5 ~ MathEx | https://www.youtube.com/watch?v=gdGmSyzR908&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=5 ~ MathEx | ||
+ | |||
+ | ===Video Solution 5=== | ||
+ | https://youtu.be/R220vbM_my8?t=899 ~ amritvignesh0719062.0 | ||
==See Also== | ==See Also== |
Latest revision as of 16:30, 8 September 2021
Contents
Problem
Let be the least positive integer greater than for which
What is the sum of the digits of ?
Solution 1
We know that by the Euclidean Algorithm. Hence, let . Subtracting the equations, . Letting , . Taking , we have . We are given . Notice that if then the condition is violated. The next possible value of satisfies the given condition, giving us the answer . Alternatively, we could have said for only, so , giving us our answer. Since the problem asks for the sum of the digits of , = or is our answer.
~Prabh1512, with edits by Terribleteeth.
Solution 2
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 the Chinese Remainder Theorem. Now, since the problem is asking for the least positive integer greater than , we find the least solution is .
However, we 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 3 (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 .
-Midnight
Solution 4 (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 .
~ Baolan
Solution 5
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. is the first number that works so we get , . . Our answer is then .
Solution 6
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 7 (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
Solution 8
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 .
-SmileKat32
Solution 9
We are able to set-up the following system-of-congruences: Therefore, by definition, we are able to set-up the following system of equations: Thus, We know and since therefore Simplifying this congruence further, we have Thus, by definition, Substituting this back into our original equation, By definition, we are able to set-up the following congruence: Thus, , so our answer is simply .
(Remarks. since by definition & since by definition.
Remember,
Lastly, the reason why is would be divisible by , which is not possible due to the certain condition.)
~ nikenissan
Solution 10
First, we find . We know that it is greater than , so we first input . From the first equation, , we know that if is correct, after we add to it, it should be divisible by , but not . Uh oh. To get to the nearest number divisible by , we have to add to cancel out the remainder. (Note that we don't subtract to get to ; is already at its lowest possible value!) Adding to gives us . (Note: is currently divisible by 63, but that's fine since we'll be changing it in the next step.)
Now using, the second equation, , we know that if is correct, after we add to it, it should be divisible by , but not . Uh oh (again). This requires some guessing and checking. We can add over and over again until is valid. This changes while also maintaining that has no remainders. After adding once, we get . By pure luck, adding two more times gives us with no remainders. We now have . However, this number is divisible by . To get the next possible number, we add the LCM of and (once again, to maintain divisibility), which is . Unfortunately, is still divisible by . Adding again gives us , which is valid. However, remember that this is equal to , so subtracting from gives us , which is .
The sum of its digits are .
So, our answer is . ~ primegn
Solution 11 (Euclidean Algorithm)
By the Euclidean Algorithm, we have Clearly, must be either or and must be
More generally, let so we get Subtracting from and then simplifying give Taking modulo produces Recall that From it follows that from which Therefore, the possible values for are
We need to check whether positive integers and (where ) exist in
- If then substituting into gives Next, substituting into produces or
There are no solutions
- If then substituting into gives Next, substituting into produces or
The solution is
Finally, the least such positive integer is The sum of its digits is
~MRENTHUSIASM
Video Solutions
Video Solution 1 (Richard Rusczyk)
https://artofproblemsolving.com/videos/amc/2020amc10a/514
Video Solution 2
https://youtu.be/8mNMKH0T9W0 - Happytwin
Video Solution 3 (Quick & Simple)
Education The Study of Everything
Video Solution 4
https://www.youtube.com/watch?v=gdGmSyzR908&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=5 ~ MathEx
Video Solution 5
https://youtu.be/R220vbM_my8?t=899 ~ amritvignesh0719062.0
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.