Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 AMC 12A Problems/Problem 23"

(→‎Solution)
(→‎Solution 2)
Line 37: Line 37:
  
 
==Solution 2==
 
==Solution 2==
−
Let <math>P</math> be <math>90!</math> after we truncate its zeros. 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.
+
Let <math>P</math> be <math>90!</math> after we truncate its zeros. Notice that <math>90!</math> has exactly <math>\floor{\frac{90}{5}} + \floor{\frac{90}{25}} = 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>
 
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>
+
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.
  
−
Notice that <math>P</math> differs from <math>90!</math> by an exponential of 10. Thus, we can "divide out" all the zeros from 10, 20, 30, ..., 90. We are left with the integers from 1 to 9, from which we multiply the non-five numbers to obtain a <math>1 \mod 25</math>. Now, we combine this 5 with the remaining 5, 15, 25, ..., 85. To divide by 10 is to cancel a 5 from a number and divide by 2. Because 25 is relatively prime to 2, we can transform the "divide by 2" into multiply by <math>2^{-1}</math> modulo 25. Thus, 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>.
+
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 ==

Revision as of 11:34, 8 August 2014

Problem

The number obtained from the last two nonzero digits of $90!$ is equal to $n$. What is $n$?

$\textbf{(A)}\ 12 \qquad \textbf{(B)}\ 32 \qquad \textbf{(C)}\ 48 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 68$

Solution

We will use the fact that for any integer $n$, \begin{align*}(5n+1)(5n+2)(5n+3)(5n+4)&=[(5n+4)(5n+1)][(5n+2)(5n+3)]\\ &=(25n^2+25n+4)(25n^2+25n+6)\equiv 4\cdot 6\\ &=24\pmod{25}\equiv -1\pmod{25}.\end{align*}

First, we find that the number of factors of $10$ in $90!$ is equal to $\left\lfloor \frac{90}5\right\rfloor+\left\lfloor\frac{90}{25}\right\rfloor=18+3=21$. Let $N=\frac{90!}{10^{21}}$. The $n$ we want is therefore the last two digits of $N$, or $N\pmod{100}$. If instead we find $N\pmod{25}$, we know that $N\pmod{100}$, what we are looking for, could be $N\pmod{25}$, $N\pmod{25}+25$, $N\pmod{25}+50$, or $N\pmod{25}+75$. Only one of these numbers will be a multiple of four, and whichever one that is will be the answer, because $N\pmod{100}$ has to be a multiple of 4.

If we divide $N$ by $5^{21}$ by taking out all the factors of $5$ in $N$, we can write $N$ as $\frac M{2^{21}}$ where \[M=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2\cdots 89\cdot 18,\] where every multiple of 5 is replaced by the number with all its factors of 5 removed. Specifically, every number in the form $5n$ is replaced by $n$, and every number in the form $25n$ is replaced by $n$.

The number $M$ can be grouped as follows:

\begin{align*}M= &(1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots(86\cdot 87\cdot 88\cdot 89)\\ &\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*}

Where the first line is composed of the numbers in $90!$ 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 $M$ to

\begin{align*}M&\equiv(-1)^{18} \cdot (-1)^3(16\cdot 17\cdot 18) \cdot (1\cdot 2\cdot 3) \\ &= 1\cdot -21\cdot 6\\ &= -1\pmod{25} =24\pmod{25}.\end{align*}

Using the fact that $2^{10}=1024\equiv -1\pmod{25}$ (or simply the fact that $2^{21}=2097152$ if you have your powers of 2 memorized), we can deduce that $2^{21}\equiv 2\pmod{25}$. Therefore $N=\frac M{2^{21}}\equiv \frac {24}2\pmod{25}=12\pmod{25}$.

Finally, combining with the fact that $N\equiv 0\pmod 4$ yields $n=\boxed{\textbf{(A)}\ 12}$.

Solution 2

Let $P$ be $90!$ after we truncate its zeros. Notice that $90!$ has exactly $\floor{\frac{90}{5}} + \floor{\frac{90}{25}} = 21$ (Error compiling LaTeX. Unknown error_msg) factors of 5; thus, \[P = 2^{-21}*5^{-21}*90!.\] We shall consider $P$ modulo 4 and 25, to determine its residue modulo 100. It is easy to prove that $P$ is divisible by 4 (consider the number of 2s dividing $90!$ minus the number of 5s dividing $90!$), and so we only need to consider $P$ modulo 25.

Now, notice that for integers $a, n$ we have\[(5n + a)(5n - a) \equiv -a^2 \mod 25.\]

Thus, for integral a: \[(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.\] Using this process, we can essentially remove all the numbers which had not formerly been a multiple of 5 in $90!$ 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 $2^{-12}$. 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 $2^{-11}$. But this is simply by Fermat's Little Theorem $2^9 = 512 \equiv 12 \mod 25$. Because 12 is also a multiple of 4, we can utilize the Chinese Remainder Theorem to show that $P = 12 \mod 100$ and so the answer is $\boxed{12}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_23&oldid=62841"