## Problem of the Day #4: Exponentiated Factorial
*March 23, 2011*

*Posted by Albert in : potd , trackback*

Determine the last three non-zero digits ofÂ $(20!)^{2000}$

**Solution:**

Consider the factorization of $20! = 2^{18} \cdot 3^8 \cdot 5^4 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19$.

We don’t want any zeros, so cancel every pair of $2$ and $5$: Let $S = 2^{14} \cdot 3^8 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19$.

Since we want to find $(20!)^{2000} \pmod{1000}$, we may employ Euler’s Totient Function on each prime factor of $S$ that is relatively prime to $1000$. For some number $a$ relatively prime to $1000$, $a^{\phi(1000)} \equiv 1 \pmod{1000}$. $a^{400} \equiv a^{2000} \equiv 1 \pmod{1000}$. This means $S^{2000} \equiv (2^{14})^{2000} \pmod{1000}$.

Now we consider the periodicity of $2^n$ in $1000$. By the Chinese Remainder Theorem, we can consider $2^n \pmod{125}$ and $2^n \pmod{8}$ separately for some integer n. Since for all $n \geq 3$, $2^n \equiv 0 \pmod{8}$, we only need to consider the periodicity of $2^n$ in $125$. To do this, we notice we want to find the first $n > 0$ for which $2^n \equiv 1 \pmod{125}$. Since $2$ is relatively prime to $125$, we can employ Euler’s Totient Function again: $2^{\phi(125)} \equiv 1 \pmod{125}$. $\phi(125) = 125(1-\frac{1}{5}) = 100$. This means the periodicity of $2^n$ in $125$ is the periodicity of $2^n$ in $1000$ is $100$.

This means $2^n \equiv 2^{n+100} \pmod{125}$, for $n \geq 0$, which means $(2^{14})^{2000} \equiv 2^0 \equiv 1 \pmod{125}$. Using the Chinese Remainder Theorem on $1 \pmod{125}$ and $0 \pmod{8}$, we find the solution is $376 \pmod{1000}$.

Thus, the answer is $\fbox{376}$.

## Comments»

no comments yet - be the first?