AMC10 2010 A

Answer (A): There are 18 factors of 90! that are multiples of 5, 3 factors that are multiples of 25, and no factors that are multiples of higher powers of 5. Also, there are more than 45 factors of 2 in 90!. Thus $90!=10^{21}N$ where $N$ is an integer not divisible by 10, and if $N\equiv n\pmod{100}$ with $0<n\le 99$, then $n$ is a multiple of 4. Let $90!=AB$ where $A$ consists of the factors that are relatively prime to 5 and $B$ consists of the factors that are divisible by 5. Note that $\prod_{j=1}^{4}(5k+j)\equiv 5k(1+2+3+4)+1\cdot2\cdot3\cdot4\equiv 24\pmod{25}$, thus $$ \begin{array}{rcl} A&=&(1\cdot2\cdot3\cdot4)\cdot(6\cdot7\cdot8\cdot9)\cdots(86\cdot87\cdot88\cdot89)\\ &\equiv&24^{18}\equiv(-1)^{18}\equiv 1\pmod{25}. \end{array} $$ Similarly, $$ B=(5\cdot10\cdot15\cdot20)\cdot(30\cdot35\cdot40\cdot45)\cdot(55\cdot60\cdot65\cdot70)\cdot(80\cdot85\cdot90)\cdot(25\cdot50\cdot75), $$ thus $$ \begin{array}{rcl} \dfrac{B}{5^{21}}&=&(1\cdot2\cdot3\cdot4)\cdot(6\cdot7\cdot8\cdot9)\cdot(11\cdot12\cdot13\cdot14)\cdot(16\cdot17\cdot18)\cdot(1\cdot2\cdot3)\\ &\equiv&24^{3}\cdot(-9)\cdot(-8)\cdot(-7)\cdot 6\equiv(-1)^{3}\cdot 1\equiv -1\pmod{25}. \end{array} $$ Finally, $2^{21}=2\cdot(2^{10})^{2}=2\cdot(1024)^{2}\equiv 2\cdot(-1)^{2}\equiv 2\pmod{25}$, so $13\cdot2^{21}\equiv 13\cdot2\equiv 1\pmod{25}$. Therefore $$ \begin{array}{rcl} N&\equiv&(13\cdot2^{21})N=13\cdot\dfrac{90!}{5^{21}}=13\cdot A\cdot\dfrac{B}{5^{21}}\equiv 13\cdot 1\cdot(-1)\pmod{25}\\ &\equiv&-13\equiv 12\pmod{25}. \end{array} $$ Thus $n$ is equal to 12, 37, 62, or 87, and because $n$ is a multiple of 4, it follows that $n=12$.