Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Partially related:… – Hans Giebenrath Apr 11 '12 at 8:30
up vote 15 down vote accepted

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.

share|cite|improve this answer
nice solution mercio... – juantheron Nov 8 '13 at 15:10
Very nice answer. But $\phi$ is not a group morphism, because its domain is not a group. It is a multiplicative map though. – Servaes Jun 26 at 19:40
At least $\phi$ is a monoid homomorphism. – awllower Jul 16 at 9:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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