Finding last two non-zero digits of 2016!

Question

Find last two non-zero digits of 2016!

I wasn't able to find anything which could help me. I need the method to solve it in the "mathematical" way, without computing the factorial itself.

Answer 1

Let $k:=2016$. Write $k!=m5^n$ with $m\in\mathbb{Z}\backslash 5\mathbb{Z}$ so $n=102$. The prime factorisation of $M:=\frac{k!}{10^n}$ is here. Since $M\in\mathbb{Z}\backslash 5\mathbb{Z}$, the answer to your question is determined by $M$ modulo 100 (hereafter $\equiv$). Apparently the answer is 04, which we can prove by brute force (but I hope someone here knows a better way). Oh, wait; if that 0 in 04 is disallowed, we need to go to mod 1000 instead by much the same technique. A comment above noted that we get 704.

A few tricks speed it up. If $p$ is an odd prime dividing $M$, $p$ is co-prime to 100 so $p^{99}\equiv 1$ by Fermat's little theorem. For example, $3^{1004}\equiv 3^{14}\equiv 69$. The power-of-2 factor is harder, viz. $2^{1508}=2^{2^2\times 13\times 29}\equiv 12^{52} = 2^{104}$ (since $2^{29}\equiv 12,\,3^4\equiv 1$). Thus $2^{1508}\equiv (-8)^{8}=2^{24}\equiv 16$.

Answer 2

Hints: I assume you are trying to find last two digits before the trailing zeroes. If you actually need the last two nonzero digits, then this method should also work (with small adjustments), albeit less effectively.

First hint:

You are trying to find the residue modulo $100$ of the number that remains after dividing by the maximal power of $10$.

Second hint:

Apply Chinese Remainder Theorem to deduce that it is enough to find the residue modulo $25$ (because the residue modulo $4$ will clearly be $0$).

Third hint:

Actually, it is enough to find the residues modulo $25$ of $24!$ and $16!$ divided by the largest powers of $10$ that divide them (or something of the sort, I haven't checked exactly), and then multiply appropriate powers of those residues.

Fourth hint:

To calculate those last residues, you can simplify the process a bit by working modulo $25$, but I can't think of any further simplification.