20
$\begingroup$

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?

$\endgroup$
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ nice solution mercio... $\endgroup$ – juantheron Nov 8 '13 at 15:10
  • 2
    $\begingroup$ Very nice answer. But $\phi$ is not a group morphism, because its domain is not a group. It is a multiplicative map though. $\endgroup$ – Servaes Jun 26 '16 at 19:40
  • 2
    $\begingroup$ At least $\phi$ is a monoid homomorphism. $\endgroup$ – awllower Jul 16 '16 at 9:26
  • 1
    $\begingroup$ What do the 3 bar and k bar mean, and why 3? Thanks $\endgroup$ – gpanda Apr 11 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.