Último dígito no cero de un factorial

Question

Me encontré con un truco genial para último dígito no cero de un factorial . En realidad se trata de una relación recurrente que establece que:

Si $D(N)$ denota el último dígito no nulo del factorial, entonces

$$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)}$$

Dónde $\left\lfloor\cdots\right\rfloor$ es la mayor función entera.

Me preguntaba si alguien podría explicar por qué funciona esto.

Answer 1

En primer lugar, sabemos que (excepto para n=0), hay más factores de 2 que factores de 5 en $n!$ para que el primer dígito no nulo tenga que ser par, y sólo necesitamos saber cuál es el módulo $5$ .

Definir $\phi : \mathbb{N}^* \to (\mathbb{Z}/5\mathbb{Z})^*$ por $\phi(n) = {\bar3}^{v_5(n)} \times d(n)$ donde $v_5(n)$ es el número de $5$ en la factorización de $n$ y $d(n)$ es la clase del último dígito no nulo de $n$ cuando se escribe en base $5$ . El objetivo es encontrar $\phi(n!)$ .

Resulta que $\phi$ es un morfismo de grupo de $(\mathbb{N}^*,\times)$ a $((\mathbb{Z}/5\mathbb{Z})^*,\times)$ :
Si $n = 5^k(a+5b)$ y $m = 5^{k'}(a'+5b')$ con $a$ y $a'$ coprima con $5$ entonces $nm = 5^{k+k'}(aa'+5(ab'+ba'+5bb'))$ Por lo tanto $\phi(nm) = 3^{k+k'}aa' = (3^k a)(3^{k'}a') = \phi(n)\phi(m)$ .

Por lo tanto, sólo tenemos que encontrar $\phi(k)$ para $k=1 \ldots n$ y los multiplicamos para obtener $\phi(n!)$ .
Si $k$ es coprima con $5$ entonces $\phi(k) = \bar{k}$ y $\phi(k) = 3 \phi(k/5)$ por otra parte. Además, $1*2*3*4 = 4$ en $(\mathbb{Z}/5\mathbb{Z})^*$ por lo que si $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!)$$

Si $n=5a+b$ entonces $\phi(n!) = \phi((5a)!)\phi(5a+1)\ldots\phi(5a+b) = \phi((5a)!)\phi(1)\ldots\phi(b) = \phi((5a)!)\phi(b!)$ Por lo tanto, tenemos la relación de recurrencia $\phi(n!) = 2^{[n/5]} \phi([n/5]!) \phi((n \mod 5)!)$

---

Ahora para obtener el dígito en base $10$ : si $n! = 10^k (a + 10 \ldots)$ con $a \in \{2;4;6;8\}$ entonces, en la base $5$ obtenemos $n! = 5^k ((2^k a) + 5 \ldots)$ Así que $\phi(n!) = 3^k*2^k * a = a$ en $(\mathbb{Z}/5\mathbb{Z})^*$ Así que simplemente tenemos que mirar $\phi(n!)$ y escoge el dígito par correspondiente:

De hecho, $((\mathbb{Z}/5\mathbb{Z})^*= \{1;2;3;4\},\times)$ es isomorfo a $(\{6;2;8;4\},\times)$ donde la multiplicación es modulo $10$ . Reescribiendo la relación de recurrencia en este contexto, obtenemos : $D(n) = 2^{[n/5]} D([n/5]) D(n \mod 5)$ donde las multiplicaciones son todas modulo $10$ .

Para recuperar la relación de recurrencia que tiene, sólo tenemos que demostrar que $2^{[n/5]} D(n \mod 5) = 4^{[n/10]} D(n \mod 10)$ :
Si el último dígito de n es menor que $5$ entonces $[n/5] = 2[n/10]$ y $n \mod 5 = n \mod 10$ así que son iguales. Si no, entonces $[n/5] = 2[n/10] +1$ y $D(n \mod 10) = D(5) D(n \mod 5) = 2 D(n \mod 5)$ para que vuelvan a ser iguales.