Difference between revisions of "2020 AMC 10A Problems/Problem 24"
MRENTHUSIASM (talk | contribs) (→Solution 10: Reformatted.) |
(Added a solution) |
||
(45 intermediate revisions by 8 users not shown) | |||
Line 10: | Line 10: | ||
== Solution 1 == | == Solution 1 == | ||
− | We know that <math>(n+57,63)=21 | + | We know that <math>\gcd(n+57,63)=21</math> and <math>\gcd(n-57, 120)= 60</math> by the Euclidean Algorithm. Hence, let <math>n+57=21\alpha</math> and <math>n-57=60 \gamma</math>, where <math>\gcd(\alpha,3)=1</math> and <math>\gcd(\gamma,2)=1</math>. Subtracting the two equations, <math>38=7\alpha-20\gamma</math>. Letting <math>\gamma = 2s+1</math>, we get <math>58=7\alpha-40s</math>. Taking modulo <math>40</math>, we have <math>\alpha \equiv{14} \pmod{40}</math>. We are given that <math>n=21\alpha -57 >1000</math>, so <math>\alpha \geq 51</math>. Notice that if <math>\alpha =54</math> then the condition <math>\gcd(\alpha,3)=1</math> is violated. The next possible value of <math>\alpha = 94</math> satisfies the given condition, giving us <math>n=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>, our answer is <math>1+9+1+7=\boxed{\textbf{(C) } 18}</math>. | |
− | + | ~Prabh1512 | |
− | |||
− | + | ==Solution 2== | |
+ | The conditions of the problem reduce to the following: <math>n+120 = 21k</math> and <math>n+63 = 60\ell</math>, where <math>\gcd(k,3) = 1</math> and <math>\gcd(\ell,2) = 1</math>. From these equations, we see that <math>21k - 60\ell = 57</math>. Solving this Diophantine equation gives us that <math>k = 20a + 17</math> and <math>\ell = 7a + 5</math>. Since, <math>n>1000</math>, we can do some bounding and get that <math>k > 53</math> and <math>\ell > 17</math>. Now we start bashing by plugging in numbers that satisfy these conditions: <math>a=4</math> is the first number that works so we get <math>\ell = 33</math>, <math>k = 97</math>. Therefore, we have <math>n=21(97)-120=60(33)-63=1917</math>, and our answer is <math>1+9+1+7=\boxed{\textbf{(C) } 18}</math>. | ||
==Solution 3== | ==Solution 3== | ||
− | + | We first find that <math>n\equiv6\pmod{21}</math> and <math>n\equiv57\pmod{60}</math>, then we get <math>n=21x+6</math> and <math>n=60y+57</math> by definitions, where <math>x</math> and <math>y</math> are integers. It follows that <math>y</math> must be odd, since the GCD will be <math>120</math> instead of <math>60</math> if <math>y</math> is even. Also, the unit digit of <math>n</math> must be <math>7</math>, since the unit digit of <math>60y</math> is always <math>0</math> and the unit digit of <math>57</math> is <math>7</math>. Therefore, we find that <math>x</math> must end in <math>1</math> to satisfy <math>n</math> having a unit digit of <math>7</math>. Also, we find that <math>x</math> must not be a multiple of <math>3</math> or else the GCD will be <math>63</math>. Therefore, we test values for <math>x</math> and find that <math>x=91</math> satisfies all these conditions. Therefore, <math>n=1917</math> and <math>1+9+1+7 = \boxed{\textbf{(C) } 18}</math>. | |
+ | |||
+ | ~happykeeper | ||
==Solution 4== | ==Solution 4== | ||
− | + | We are given that <math>\gcd(63, n+120) =21</math> and <math>\gcd(n+63, 120)=60.</math> By applying the Euclidean algorithm 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 are given that <math>\gcd(63, n+120) =21</math> and <math>\gcd(n+63, 120)=60.</math> By applying the Euclidean algorithm | ||
− | We now know that <math>n+183</math> must be divisible by <math>21</math> and <math>60,</math> so it is divisible by <math>\text{lcm}(21, 60) = 420.</math> Therefore, <math>n+183 = 420k</math> for some integer <math>k.</math> We know that <math>3 \nmid k,</math> or else the first condition won't hold (<math>\gcd</math> will be <math>63</math>) and <math>2 \nmid k,</math> or else the second condition won't hold (<math>\gcd</math> will be <math>120</math>). Since <math>k = 1</math> gives us too small of an answer, then <math>k=5 | + | We now know that <math>n+183</math> must be divisible by <math>21</math> and <math>60,</math> so it is divisible by <math>\text{lcm}(21, 60) = 420.</math> Therefore, <math>n+183 = 420k</math> for some integer <math>k.</math> We know that <math>3 \nmid k,</math> or else the first condition won't hold (<math>\gcd</math> will be <math>63</math>) and <math>2 \nmid k,</math> or else the second condition won't hold (<math>\gcd</math> will be <math>120</math>). Since <math>k = 1</math> gives us too small of an answer, then <math>k=5,</math> from which <math>n = 1917.</math> So, the answer is <math>1+9+1+7 = \boxed{\textbf{(C) } 18}.</math> |
− | ==Solution | + | ==Solution 5== |
− | <math>\gcd(n+63,120)=60</math> tells us <math>n+63\equiv60\pmod {120}</math>. The smallest <math>n+63</math> that satisfies the previous condition and <math>n>1000</math> is <math>1140</math>, so we start from there. If <math>n+63=1140</math>, then <math>n+120=1197</math>. Because <math>\gcd(n+120,63)=21</math>, <math>n+120\equiv21\pmod {63}</math> or <math>n+120\equiv42\pmod {63}</math>. We see that <math>1197\equiv0\pmod {63}</math>, which does not fulfill the requirement for <math>n+120</math>, so we continue by keep on adding <math>120</math> to <math>1197</math>, in order to also fulfill the requirement for <math>n+63</math>. Soon, we see that <math>n+120\pmod {63}</math> decreases by <math>6</math> every time we add <math>120</math>, so we can quickly see that <math>n=1917</math> because at that point <math>n+120\equiv21\pmod {63}</math>. We add up all digits of <math>1917</math> | + | <math>\gcd(n+63,120)=60</math> tells us <math>n+63\equiv60\pmod {120}</math>. The smallest <math>n+63</math> that satisfies the previous condition and <math>n>1000</math> is <math>1140</math>, so we start from there. If <math>n+63=1140</math>, then <math>n+120=1197</math>. Because <math>\gcd(n+120,63)=21</math>, <math>n+120\equiv21\pmod {63}</math> or <math>n+120\equiv42\pmod {63}</math>. We see that <math>1197\equiv0\pmod {63}</math>, which does not fulfill the requirement for <math>n+120</math>, so we continue by keep on adding <math>120</math> to <math>1197</math>, in order to also fulfill the requirement for <math>n+63</math>. Soon, we see that <math>n+120\pmod {63}</math> decreases by <math>6</math> every time we add <math>120</math>, so we can quickly see that <math>n=1917</math> because at that point <math>n+120\equiv21\pmod {63}</math>. We add up all digits of <math>1917</math> to get <math>\boxed{\textbf{(C) } 18}</math>. |
~SmileKat32 | ~SmileKat32 | ||
− | ==Solution | + | ==Solution 6== |
We are able to set up the following system of congruences: | We are able to set up the following system of congruences: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
Line 63: | Line 62: | ||
Lastly, the reason why <math>n \neq 1077</math> is <math>n + 120</math> would be divisible by <math>63</math>, which is not possible due to the certain condition. | Lastly, the reason why <math>n \neq 1077</math> is <math>n + 120</math> would be divisible by <math>63</math>, which is not possible due to the certain condition. | ||
− | ~nikenissan | + | ~nikenissan ~Midnight |
− | == Solution | + | == Solution 7== |
First, we find <math>n</math>. We know that it is greater than <math>1000</math>, so we first input <math>n = 1000</math>. From the first equation, <math>\gcd(63, n + 120) = 21</math>, we know that if <math>n</math> is correct, after we add <math>120</math> to it, it should be divisible by <math>21</math>, but not <math>63</math>: | First, we find <math>n</math>. We know that it is greater than <math>1000</math>, so we first input <math>n = 1000</math>. From the first equation, <math>\gcd(63, n + 120) = 21</math>, we know that if <math>n</math> is correct, after we add <math>120</math> to it, it should be divisible by <math>21</math>, but not <math>63</math>: | ||
<cmath>\frac{n + 120}{21} = \frac{1120}{21} = 53\text{ R }7.</cmath> | <cmath>\frac{n + 120}{21} = \frac{1120}{21} = 53\text{ R }7.</cmath> | ||
− | + | This does not work. To get to the nearest number divisible by <math>21</math>, we have to add <math>14</math> to cancel out the remainder. (Note that we don't subtract <math>7</math> to get to <math>53</math>; <math>n</math> is already at its lowest possible value!) | |
Adding <math>14</math> to <math>1000</math> gives us <math>n = 1014</math>. (Note: <math>n</math> is currently divisible by 63, but that's fine since we'll be changing it in the next step.) | Adding <math>14</math> to <math>1000</math> gives us <math>n = 1014</math>. (Note: <math>n</math> is currently divisible by 63, but that's fine since we'll be changing it in the next step.) | ||
− | Now using | + | Now using the second equation, <math>\gcd(n + 63, 120) = 60</math>, we know that if <math>n</math> is correct, then <math>n+63</math> is divisible by <math>60</math> but not <math>120</math>: |
<cmath>\frac{n + 63}{60} = \frac{1077}{60} = 17\text{ R }57.</cmath> | <cmath>\frac{n + 63}{60} = \frac{1077}{60} = 17\text{ R }57.</cmath> | ||
− | + | Again, this does not work. This requires some guessing and checking. We can add <math>21</math> over and over again until <math>n</math> is valid. This changes <math>n</math> while also maintaining that <math>\frac{n + 120}{21}</math> has no remainders. | |
After adding <math>21</math> once, we get <math>18 r 18</math>. By pure luck, adding <math>21</math> two more times gives us <math>19</math> with no remainders. | After adding <math>21</math> once, we get <math>18 r 18</math>. By pure luck, adding <math>21</math> two more times gives us <math>19</math> with no remainders. | ||
We now have <math>1077 + 21 + 21 + 21 = 1140</math>. However, this number is divisible by <math>120</math>. To get the next possible number, we add the LCM of <math>21</math> and <math>60</math> (once again, to maintain divisibility), which is <math>420</math>. Unfortunately, <math>1140 + 420 = 1560</math> is still divisible by <math>120</math>. Adding <math>420</math> again gives us <math>1980</math>, which is valid. However, remember that this is equal to <math>n + 63</math>, so subtracting <math>63</math> from <math>1980</math> gives us <math>1917</math>, which is <math>n</math>. | We now have <math>1077 + 21 + 21 + 21 = 1140</math>. However, this number is divisible by <math>120</math>. To get the next possible number, we add the LCM of <math>21</math> and <math>60</math> (once again, to maintain divisibility), which is <math>420</math>. Unfortunately, <math>1140 + 420 = 1560</math> is still divisible by <math>120</math>. Adding <math>420</math> again gives us <math>1980</math>, which is valid. However, remember that this is equal to <math>n + 63</math>, so subtracting <math>63</math> from <math>1980</math> gives us <math>1917</math>, which is <math>n</math>. | ||
− | The sum of its digits are <math>1 + 9 + 1 + 7 = \boxed{\textbf{(C) }18}</math>. | + | The sum of its digits are <math>1 + 9 + 1 + 7 = \boxed{\textbf{(C) } 18}</math>. |
~primegn | ~primegn | ||
− | ==Solution | + | ==Solution 8 (Euclidean Algorithm)== |
By the Euclidean Algorithm, we have | By the Euclidean Algorithm, we have | ||
<cmath>\begin{alignat*}{8} | <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, | + | \gcd(63,n+120)&=\hspace{1mm}&&\gcd(63,\phantom{ }\underbrace{n+120-63k_1}_{(n+120) \ \mathrm{mod} \ 63}\phantom{ })&&=21, \\ |
− | \gcd(n+63,120)&=&&\gcd(\phantom{ }\underbrace{n+63-120k_2}_{(n+63) \ \mathrm{mod} \ 120}\phantom{ },120)&&=60. | + | \gcd(n+63,120)&=&&\gcd(\phantom{ }\underbrace{n+63-120k_2}_{(n+63) \ \mathrm{mod} \ 120}\phantom{ },120)&&=60. |
\end{alignat*}</cmath> | \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> | 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> | ||
Line 92: | Line 91: | ||
More generally, let <math>t\in\{1,2\},</math> so we get | More generally, let <math>t\in\{1,2\},</math> so we get | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | n+120-63k_1&=21t, &\hspace{55.5mm}(1 | + | n+120-63k_1&=21t, &\hspace{55.5mm}(1) \\ |
− | n+63-120k_2&=60. &\hspace{55.5mm}(2 | + | n+63-120k_2&=60. &\hspace{55.5mm}(2) |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Subtracting <math>(2 | + | Subtracting <math>(2)</math> from <math>(1)</math> and then simplifying give |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
57-63k_1+120k_2&=21t-60 \\ | 57-63k_1+120k_2&=21t-60 \\ | ||
Line 106: | Line 105: | ||
k_2&\equiv2\pmod{7}. | k_2&\equiv2\pmod{7}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Recall that <math>n>1000.</math> From <math>(2 | + | 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 | + | 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;"> | <ul style="margin-left: 1.5em, list-style-type: square;"> | ||
− | <li>If <math>k_2=9,</math> then substituting into <math>(2 | + | <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> | There are no solutions <math>(k_1,t).</math></li><p> | ||
− | <li>If <math>k_2=16,</math> then substituting into <math>(2 | + | <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> | The solution is <math>(k_1,t)=(32,1).</math></li><p> | ||
</ul> | </ul> | ||
Line 119: | Line 118: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | == Solution | + | == Solution 9 (Euclidean Algorithm) == |
Because we are finding value of <math>n</math> for <math>n > 1000</math>, let <math>n = 1000 + k</math>. | Because we are finding value of <math>n</math> for <math>n > 1000</math>, let <math>n = 1000 + k</math>. | ||
− | Using the | + | Using the Euclidean Algorithm, |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | \gcd(63, n+120) &= \gcd(63, 1000 + k + 120) = \gcd(63, k + 1120 - 63 \cdot 18) = \gcd(63, k-14) = 21, \\ | + | \gcd(63, n+120) &= \gcd(63, 1000 + k + 120) \\ |
− | \gcd(n+63, 120) &= \gcd(k + 1000 + 63, 120) = \gcd(k + 1000 + 63 - 120 \cdot 9, 120) = \gcd(k-17, 120) = 60. | + | &= \gcd(63, k + 1120 - 63 \cdot 18) \\ |
+ | &= \gcd(63, k-14) \\ | ||
+ | &= 21, \\ | ||
+ | \gcd(n+63, 120) &= \gcd(k + 1000 + 63, 120) \\ | ||
+ | &= \gcd(k + 1000 + 63 - 120 \cdot 9, 120) \\ | ||
+ | &= \gcd(k-17, 120) \\ | ||
+ | &= 60. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
So, we have | So, we have | ||
Line 133: | Line 138: | ||
k &\equiv 17 \pmod{60}. | k &\equiv 17 \pmod{60}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Let <math>k = 21p + 14 = 60q + 17</math>, <math>7p= 20q + 1</math>, <math>7p = 21q - (q - 1)</math>, <math>q - 1</math> is a multiple of <math>7</math>. | + | Let <math>k = 21p + 14 = 60q + 17</math>, <math>7p= 20q + 1</math> (by the Division Algorithm), <math>7p = 21q - (q - 1)</math>, <math>q - 1</math> is a multiple of <math>7</math>. |
Let <math>q-1 = 7r</math>, <math>q = 7r+1</math>, <math>k = 60(7r+1) + 17 = 420r + 77</math>. | Let <math>q-1 = 7r</math>, <math>q = 7r+1</math>, <math>k = 60(7r+1) + 17 = 420r + 77</math>. | ||
Line 141: | Line 146: | ||
By substituting <math>1077</math>, <math>1497</math>, <math>1917</math> into <math>\gcd(63, n+120) =21</math> and <math>\gcd(n+63, 120)=60</math>, <math>1077</math> and <math>1497</math> aren't valid answers, only <math>1917</math> is. Therefore, the answer is <math>1+9+1+7=\boxed{\textbf{(C) } 18}</math>. | By substituting <math>1077</math>, <math>1497</math>, <math>1917</math> into <math>\gcd(63, n+120) =21</math> and <math>\gcd(n+63, 120)=60</math>, <math>1077</math> and <math>1497</math> aren't valid answers, only <math>1917</math> is. Therefore, the answer is <math>1+9+1+7=\boxed{\textbf{(C) } 18}</math>. | ||
− | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | + | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] (Solution) |
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Plainoldnumbertheory Plainoldnumbertheory] (Minor Edits) | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Plainoldnumbertheory Puck_0] (Formatting) | ||
− | == Solution | + | == Solution 10 (Diophantine Equations)== |
We know <math>63 = 3 \cdot 21</math>, and <math>\gcd(63, n + 120) = 21 \Longrightarrow n + 120 = 21a</math>, where <math>a</math> is not a multiple of <math>3</math>. | We know <math>63 = 3 \cdot 21</math>, and <math>\gcd(63, n + 120) = 21 \Longrightarrow n + 120 = 21a</math>, where <math>a</math> is not a multiple of <math>3</math>. | ||
Line 161: | Line 170: | ||
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
− | == Solution | + | == Solution 11 (Chinese Remainder Theorem) == |
We have | We have | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
Line 187: | Line 196: | ||
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | == Solution 12 (Logically Bashing) == | ||
+ | We know that <math>n</math> ends with the number <math>7</math>, since <math>n+63</math> is divisible by <math>60</math>, and any number divisible by <math>10</math> (a factor of <math>60</math>) must end with a <math>0</math>. As a result, <math>n+120</math> must also end in <math>7</math>. Because <math>n+63</math> must be divisible by <math>20</math>, as well (using the same gcd), the tens value of <math>n</math> must be odd. Also, <math>n+120</math> cannot be divisible by <math>9</math>, otherwise, its gcd with <math>63</math> will be <math>63</math>, instead of <math>21</math>. | ||
+ | |||
+ | Now, we can start bashing, using the <math>\gcd(63, n+120) =21</math>. We are given that <math>n</math> must be greater than <math>1000</math>, so we can try <math>n+120</math> that is greater than <math>1120</math>. | ||
+ | |||
+ | We try <math>21 \cdot 67</math>, but it has an even tens digit. We then can try the next highest, using <math>77</math>, but the <math>\gcd(n+63, 120) =120</math>, instead of <math>60</math>. | ||
+ | |||
+ | Since <math>87</math> is divisible by <math>3</math>, so when multiplied by <math>21</math>, it will be divisible by <math>9</math>, we do not have to test it. | ||
+ | |||
+ | The next biggest is <math>97</math>, which works and gives us <math>n=1917</math>, which, when the digits are added up, equals <math>\boxed{\textbf{(C) } 18}</math>. | ||
+ | |||
+ | ~parmani | ||
==Video Solutions== | ==Video Solutions== | ||
===Video Solution 1 (Richard Rusczyk)=== | ===Video Solution 1 (Richard Rusczyk)=== | ||
− | https:// | + | https://www.youtube.com/watch?v=tk3yOGG2K-s& |
===Video Solution 2=== | ===Video Solution 2=== | ||
Line 205: | Line 227: | ||
===Video Solution 5=== | ===Video Solution 5=== | ||
https://youtu.be/R220vbM_my8?t=899 ~ amritvignesh0719062.0 | https://youtu.be/R220vbM_my8?t=899 ~ amritvignesh0719062.0 | ||
+ | |||
+ | ==Video Solution 6== | ||
+ | https://youtu.be/YcXsdSKVywk | ||
+ | |||
+ | ~savannahsolver | ||
==See Also== | ==See Also== |
Latest revision as of 18:33, 31 August 2024
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2
- 4 Solution 3
- 5 Solution 4
- 6 Solution 5
- 7 Solution 6
- 8 Solution 7
- 9 Solution 8 (Euclidean Algorithm)
- 10 Solution 9 (Euclidean Algorithm)
- 11 Solution 10 (Diophantine Equations)
- 12 Solution 11 (Chinese Remainder Theorem)
- 13 Solution 12 (Logically Bashing)
- 14 Video Solutions
- 15 Video Solution 6
- 16 See Also
Problem
Let be the least positive integer greater than for which
What is the sum of the digits of ?
Solution 1
We know that and by the Euclidean Algorithm. Hence, let and , where and . Subtracting the two equations, . Letting , we get . Taking modulo , we have . We are given that , so . Notice that if then the condition is violated. The next possible value of satisfies the given condition, giving us .
Alternatively, we could have said for only, so , giving us our answer. Since the problem asks for the sum of the digits of , our answer is .
~Prabh1512
Solution 2
The conditions of the problem reduce to the following: and , where and . From these equations, we see that . Solving this Diophantine equation gives us that and . Since, , we can do some bounding and get that and . Now we start bashing by plugging in numbers that satisfy these conditions: is the first number that works so we get , . Therefore, we have , and our answer is .
Solution 3
We first find that and , then we get and by definitions, where and are integers. It follows that must be odd, since the GCD will be instead of if is even. Also, the unit digit of must be , since the unit digit of is always and the unit digit of is . Therefore, we find that must end in to satisfy having a unit digit of . Also, we find that must not be a multiple of or else the GCD will be . Therefore, we test values for and find that satisfies all these conditions. Therefore, and .
~happykeeper
Solution 4
We are given that and By applying the Euclidean algorithm 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 from which So, the answer is
Solution 5
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 . We add up all digits of to get .
~SmileKat32
Solution 6
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 have from which We know and since therefore Simplifying this congruence further, we have Thus, by definition, Substituting this back into our original equation, we get By definition, we are able to set up the following congruence: Thus, , so our answer is simply .
Remark
Since we conclude that
Since we conclude that
Remember that
Lastly, the reason why is would be divisible by , which is not possible due to the certain condition.
~nikenissan ~Midnight
Solution 7
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 : This does not work. 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, then is divisible by but not : Again, this does not work. 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 .
~primegn
Solution 8 (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
Solution 9 (Euclidean Algorithm)
Because we are finding value of for , let .
Using the Euclidean Algorithm, So, we have Let , (by the Division Algorithm), , is a multiple of .
Let , , .
, .
By substituting , , into and , and aren't valid answers, only is. Therefore, the answer is .
~isabelchen (Solution)
~Plainoldnumbertheory (Minor Edits)
~Puck_0 (Formatting)
Solution 10 (Diophantine Equations)
We know , and , where is not a multiple of .
Also, , and , where is not a multiple of .
Let , , .
Now the problem becomes and .
Meaning has to be a multiple of but not , and is a multiple of but not .
Using trial and error, the least values are and .
Therefore, the answer is .
Solution 11 (Chinese Remainder Theorem)
We have So, we conclude that and , respectively.
Because the moduli and are not relatively prime, namely , , and , we convert the system of linear congruences with non-coprime moduli into a system of linear congruences with coprime moduli: By Chinese Remainder Theorem, the general solution of system of linear congruences is We construct the following table: Only satisfies and . Therefore, the answer is .
Solution 12 (Logically Bashing)
We know that ends with the number , since is divisible by , and any number divisible by (a factor of ) must end with a . As a result, must also end in . Because must be divisible by , as well (using the same gcd), the tens value of must be odd. Also, cannot be divisible by , otherwise, its gcd with will be , instead of .
Now, we can start bashing, using the . We are given that must be greater than , so we can try that is greater than .
We try , but it has an even tens digit. We then can try the next highest, using , but the , instead of .
Since is divisible by , so when multiplied by , it will be divisible by , we do not have to test it.
The next biggest is , which works and gives us , which, when the digits are added up, equals .
~parmani
Video Solutions
Video Solution 1 (Richard Rusczyk)
https://www.youtube.com/watch?v=tk3yOGG2K-s&
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
Video Solution 6
~savannahsolver
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.