Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Partially related: math.stackexchange.com/questions/111385/… –  Hans Giebenrath Apr 11 '12 at 8:30

1 Answer 1

up vote 8 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 writen 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|improve this answer
    
nice solution mercio... –  juantheron Nov 8 '13 at 15:10

Your Answer

 
discard

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.