Difference between revisions of "2010 AMC 12A Problems/Problem 23"
m (debug error) |
(→Hints and Method of Attack) |
||
(14 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
+ | {{duplicate|[[2010 AMC 12A Problems|2010 AMC 12A #23]] and [[2010 AMC 10A Problems|2010 AMC 10A #24]]}} | ||
+ | |||
== Problem == | == Problem == | ||
Line 5: | Line 7: | ||
<math>\textbf{(A)}\ 12 \qquad \textbf{(B)}\ 32 \qquad \textbf{(C)}\ 48 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 68</math> | <math>\textbf{(A)}\ 12 \qquad \textbf{(B)}\ 32 \qquad \textbf{(C)}\ 48 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 68</math> | ||
− | == Solution == | + | == Hints and Method of Attack == |
+ | Let <math>P</math> be the result of dividing <math>90!</math> by tens such that <math>P</math> is not divisible by <math>10</math>. We want to consider <math>P \mod 100</math>. But because <math>100</math> is not prime, and because <math>P</math> is obviously divisible by <math>4</math> (if in doubt, look at the answer choices), we only need to consider <math>P \mod 25</math>. | ||
+ | |||
+ | However, <math>25</math> is a very particular number. <math>1 * 2 * 3 * 4 \equiv -1 \mod 25</math>, and so is <math>6 * 7 * 8 * 9</math>. How can we group terms to take advantage of this fact? | ||
+ | |||
+ | There might be a problem when you cancel out the <math>10</math>s from <math>90!</math>. One method is to cancel out a factor of <math>2</math> from an existing number along with a factor of <math>5</math>. But this might prove cumbersome, as the grouping method will not be as effective. Instead, take advantage of ''inverses'' in modular arithmetic. Just leave the negative powers of <math>2</math> in a "storage base," and take care of the other terms first. Then, use Fermat's Little Theorem to solve for the power of <math>2</math>. | ||
+ | |||
+ | == Solution 1== | ||
We will use the fact that for any integer <math>n</math>, | We will use the fact that for any integer <math>n</math>, | ||
Line 12: | Line 21: | ||
&=24\pmod{25}\equiv -1\pmod{25}.\end{align*}</cmath> | &=24\pmod{25}\equiv -1\pmod{25}.\end{align*}</cmath> | ||
− | First, we find that the number of factors of <math>10</math> in <math>90!</math> is equal to <math>\left\lfloor \frac{90}5\right\rfloor+\left\lfloor\frac{90}{25}\right\rfloor=18+3=21</math>. Let <math>N=\frac{90!}{10^{21}}</math>. The <math>n</math> we want is therefore the last two digits of <math>N</math>, or <math>N\pmod{100}</math>. | + | First, we find that the number of factors of <math>10</math> in <math>90!</math> is equal to <math>\left\lfloor \frac{90}5\right\rfloor+\left\lfloor\frac{90}{25}\right\rfloor=18+3=21</math>. Let <math>N=\frac{90!}{10^{21}}</math>. The <math>n</math> we want is therefore the last two digits of <math>N</math>, or <math>N\pmod{100}</math>. If instead we find <math>N\pmod{25}</math>, we know that <math>N\pmod{100}</math>, what we are looking for, could be <math>N\pmod{25}</math>, <math>N\pmod{25}+25</math>, <math>N\pmod{25}+50</math>, or <math>N\pmod{25}+75</math>. Only one of these numbers will be a multiple of four, and whichever one that is will be the answer, because <math>N\pmod{100}</math> has to be a multiple of 4. |
If we divide <math>N</math> by <math>5^{21}</math> by taking out all the factors of <math>5</math> in <math>N</math>, we can write <math>N</math> as <math>\frac M{2^{21}}</math> where | If we divide <math>N</math> by <math>5^{21}</math> by taking out all the factors of <math>5</math> in <math>N</math>, we can write <math>N</math> as <math>\frac M{2^{21}}</math> where | ||
Line 23: | Line 32: | ||
&\cdot (1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots (16\cdot 17\cdot 18) \\ | &\cdot (1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots (16\cdot 17\cdot 18) \\ | ||
&\cdot (1\cdot 2\cdot 3).\end{align*}</cmath> | &\cdot (1\cdot 2\cdot 3).\end{align*}</cmath> | ||
+ | |||
+ | Where the first line is composed of the numbers in <math>90!</math> that aren't multiples of five, the second line is the multiples of five '''and not 25''' after they have been divided by five, and the third line is multiples of 25 after they have been divided by 25. | ||
Using the identity at the beginning of the solution, we can reduce <math>M</math> to | Using the identity at the beginning of the solution, we can reduce <math>M</math> to | ||
Line 33: | Line 44: | ||
Finally, combining with the fact that <math>N\equiv 0\pmod 4</math> yields <math>n=\boxed{\textbf{(A)}\ 12}</math>. | Finally, combining with the fact that <math>N\equiv 0\pmod 4</math> yields <math>n=\boxed{\textbf{(A)}\ 12}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | Let <math>P</math> be <math>90!</math> after we truncate its zeros. Notice that <math>90!</math> has exactly (floored) <math>\left\lfloor\frac{90}{5}\right\rfloor + \left\lfloor\frac{90}{25}\right\rfloor = 21</math> factors of 5; thus, <cmath>P = 2^{-21}*5^{-21}*90!.</cmath> We shall consider <math>P</math> modulo 4 and 25, to determine its residue modulo 100. It is easy to prove that <math>P</math> is divisible by 4 (consider the number of 2s dividing <math>90!</math> minus the number of 5s dividing <math>90!</math>), and so we only need to consider <math>P</math> modulo 25. | ||
+ | |||
+ | Now, notice that for integers <math>a, n</math> we have<cmath>(5n + a)(5n - a) \equiv -a^2 \mod 25.</cmath> | ||
+ | |||
+ | Thus, for integral a: <cmath>(10a + 1)(10a + 2)(10a + 3)(10a + 4)(10a + 6)(10a + 7)(10a + 8)(10a + 9) \equiv (-1)(-4)(-9)(-16) \equiv 576 \equiv 1 \mod 25.</cmath> Using this process, we can essentially remove all the numbers which had not formerly been a multiple of 5 in <math>90!</math> from consideration. | ||
+ | |||
+ | Now, we consider the remnants of the 5, 10, 15, 20, ..., 90 not yet eliminated. The 10, 20, 30, ..., 90 becomes 1, 2, 3, 4, 1, 6, 7, 8, 9, whose product is 1 mod 25. Also, the 5, 5, 15, 25, ..., 85 becomes 1, 1, 3, 1, 7, 9, 11, 13, 3, 17 and <math>2^{-12}</math>. We deduce that from multiplying out the 1, 1, 3, 1, 7, ..., 17 is equivalent to 2 modulo 25, and so we need to compute <math>2^{-11}</math>. But this is simply by Fermat's Little Theorem <math>2^9 = 512 \equiv 12 \mod 25</math>. Because 12 is also a multiple of 4, we can utilize the Chinese Remainder Theorem to show that <math>P = 12 \mod 100</math> and so the answer is <math>\boxed{12}</math>. | ||
== See also == | == See also == | ||
Line 38: | Line 58: | ||
[[Category:Intermediate Number Theory Problems]] | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 16:21, 10 August 2020
- The following problem is from both the 2010 AMC 12A #23 and 2010 AMC 10A #24, so both problems redirect to this page.
Problem
The number obtained from the last two nonzero digits of is equal to . What is ?
Hints and Method of Attack
Let be the result of dividing by tens such that is not divisible by . We want to consider . But because is not prime, and because is obviously divisible by (if in doubt, look at the answer choices), we only need to consider .
However, is a very particular number. , and so is . How can we group terms to take advantage of this fact?
There might be a problem when you cancel out the s from . One method is to cancel out a factor of from an existing number along with a factor of . But this might prove cumbersome, as the grouping method will not be as effective. Instead, take advantage of inverses in modular arithmetic. Just leave the negative powers of in a "storage base," and take care of the other terms first. Then, use Fermat's Little Theorem to solve for the power of .
Solution 1
We will use the fact that for any integer ,
First, we find that the number of factors of in is equal to . Let . The we want is therefore the last two digits of , or . If instead we find , we know that , what we are looking for, could be , , , or . Only one of these numbers will be a multiple of four, and whichever one that is will be the answer, because has to be a multiple of 4.
If we divide by by taking out all the factors of in , we can write as where where every multiple of 5 is replaced by the number with all its factors of 5 removed. Specifically, every number in the form is replaced by , and every number in the form is replaced by .
The number can be grouped as follows:
Where the first line is composed of the numbers in that aren't multiples of five, the second line is the multiples of five and not 25 after they have been divided by five, and the third line is multiples of 25 after they have been divided by 25.
Using the identity at the beginning of the solution, we can reduce to
Using the fact that (or simply the fact that if you have your powers of 2 memorized), we can deduce that . Therefore .
Finally, combining with the fact that yields .
Solution 2
Let be after we truncate its zeros. Notice that has exactly (floored) factors of 5; thus, We shall consider modulo 4 and 25, to determine its residue modulo 100. It is easy to prove that is divisible by 4 (consider the number of 2s dividing minus the number of 5s dividing ), and so we only need to consider modulo 25.
Now, notice that for integers we have
Thus, for integral a: Using this process, we can essentially remove all the numbers which had not formerly been a multiple of 5 in from consideration.
Now, we consider the remnants of the 5, 10, 15, 20, ..., 90 not yet eliminated. The 10, 20, 30, ..., 90 becomes 1, 2, 3, 4, 1, 6, 7, 8, 9, whose product is 1 mod 25. Also, the 5, 5, 15, 25, ..., 85 becomes 1, 1, 3, 1, 7, 9, 11, 13, 3, 17 and . We deduce that from multiplying out the 1, 1, 3, 1, 7, ..., 17 is equivalent to 2 modulo 25, and so we need to compute . But this is simply by Fermat's Little Theorem . Because 12 is also a multiple of 4, we can utilize the Chinese Remainder Theorem to show that and so the answer is .
See also
2010 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 22 |
Followed by Problem 24 |
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 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.