number theory - Last non Zero digit of a Factorial

I ran into a cool trick for last non zero digit of a factorial. This is actually a recurrent relation which states that:

If $D(N)$ denotes the last non zero digit of factorial, then

$$D(N)=4D\left(\left\lfloor{\frac N5}\right\rfloor\right)\cdot D(\mbox{Units digit of $N$}) \qquad \mbox{(If tens digit of $N$ is odd)}$$
$$D(N)=6D\left(\left\lfloor{\frac N5}\right\rfloor\right)\cdot D(\mbox{Units digit of $N$}) \qquad \mbox{(If tens digit of $N$ is even)}$$

Where $\left\lfloor\cdots\right\rfloor$ is greatest integer function.

I was wondering, if anybody could explain why this works?

Answer

First, we know that (except for n=0), there are more factors of 2 than factors of 5 in $n!$, so that the first non zero digit has to be even, and we only need to know what it is modulo $5$.

Define $\phi : \mathbb{N}^* \to (\mathbb{Z}/5\mathbb{Z})^*$ by $\phi(n) = {\bar3}^{v_5(n)} \times d(n)$ where $v_5(n)$ is the number of $5$ in the factorisation of $n$ and $d(n)$ is the class of the last nonzero digit of $n$ when written in base $5$. The goal is to find $\phi(n!)$.

It turns out that $\phi$ is a group morphism from $(\mathbb{N}^*,\times)$ to $((\mathbb{Z}/5\mathbb{Z})^*,\times)$ :
If $n = 5^k(a+5b)$ and $m = 5^{k'}(a'+5b')$ with $a$ and $a'$ coprime with $5$, then $nm = 5^{k+k'}(aa'+5(ab'+ba'+5bb'))$, thus $\phi(nm) = 3^{k+k'}aa' = (3^k a)(3^{k'}a') = \phi(n)\phi(m)$.

Therefore we only need to find $\phi(k)$ for $k=1 \ldots n$ and multiply them together to get $\phi(n!)$.
If $k$ is coprime with $5$, then $\phi(k) = \bar{k}$, and $\phi(k) = 3 \phi(k/5)$ otherwise.
Furthermore, $1*2*3*4 = 4$ in $(\mathbb{Z}/5\mathbb{Z})^*$ so if $n=5a$ :

$$\phi(n!) = \left(\prod_{i=0}^{a-1} \phi(5i+1)\ldots\phi(5i+5)\right) = \left(\prod_{i=0}^{a-1} 3 \cdot 1 \cdot 2 \cdot 3 \cdot 4 \cdot \phi(i+1)\right) \\ = \left(\prod_{i=0}^{a-1} 2 \phi(i+1)\right) = 2^a\phi(a!)$$

If $n=5a+b$, then $\phi(n!) = \phi((5a)!)\phi(5a+1)\ldots\phi(5a+b) = \phi((5a)!)\phi(1)\ldots\phi(b) = \phi((5a)!)\phi(b!)$
Therefore, we have the recurrence relation $\phi(n!) = 2^{[n/5]} \phi([n/5]!) \phi((n \mod 5)!)$

---

Now to get the digit in base $10$ : if $n! = 10^k (a + 10 \ldots)$ with $a \in \{2;4;6;8\}$ then, in base $5$, we get $n! = 5^k ((2^k a) + 5 \ldots)$, so $\phi(n!) = 3^k*2^k * a = a$ in $(\mathbb{Z}/5\mathbb{Z})^*$
So we simply need to look at $\phi(n!)$ and pick the corresponding even digit :

In fact, $((\mathbb{Z}/5\mathbb{Z})^*= \{1;2;3;4\},\times)$ is isomorphic to $(\{6;2;8;4\},\times)$ where the multiplication is modulo $10$.

Rewriting the recurrence relation in this context, we get :
$D(n) = 2^{[n/5]} D([n/5]) D(n \mod 5)$ where the multiplications are all modulo $10$.

To recover the recurrence relation you have, we only need to prove that $2^{[n/5]} D(n \mod 5) = 4^{[n/10]} D(n \mod 10)$ :
If the last digit of n is less than $5$, then $[n/5] = 2[n/10]$ and $n \mod 5 = n \mod 10$, so they are equal.
If not, then $[n/5] = 2[n/10] +1$ and $D(n \mod 10) = D(5) D(n \mod 5) = 2 D(n \mod 5)$ so they are equal again.