Potencia más alta de un primo $p$ dividiendo $N!$

Question

¿Cómo se encuentra la mayor potencia de un primo $p$ que divide $N!$ y otros productos relacionados?

Pregunta relacionada: ¿Cuántos ceros hay al final de $N!$ ?

---

Esto se hace para reducir las duplicaciones de resúmenes. Véase Cómo hacer frente a las preguntas duplicadas *abstractas*. y Lista de generalizaciones de preguntas comunes para más detalles.

Answer 1

La mayor potencia de un primo que divide $N!$

En general, la mayor potencia de un primo $p$ dividiendo $N!$ viene dada por

$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

El primer término aparece ya que se quiere contar el número de términos menores que $N$ y son múltiplos de $p$ y cada una de ellas aporta una $p$ a $N!$ . Pero entonces cuando tienes múltiplos de $p^2$ no estás multiplicando sólo una $p$ pero estás multiplicando dos de estos primos $p$ al producto. Así que ahora se cuenta el número de múltiplos de $p^2$ menos de $N$ y añadirlos. Esto se recoge en el segundo término $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$ . Repite esto para tener en cuenta las potencias más altas de $p$ menos de $N$ .

Número de ceros al final de $N!$

El número de ceros al final de $N!$ viene dada por $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ donde $\left \lfloor \frac{x}{y} \right \rfloor$ es el mayor número entero $\leq \frac{x}{y}$ .

Para que quede claro, escriba $N!$ como producto de primos $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ donde $\alpha_i \in \mathbb{N}$ .

Tenga en cuenta que $\alpha_5 < \alpha_2$ siempre que $N \geq 2$ . (¿Por qué?)

El número de ceros al final de $N!$ es la mayor potencia de $10$ dividiendo $N!$

Si $10^{\alpha}$ divide $N!$ y como $10 = 2 \times 5$ , $2^{\alpha} | N!$ y $5^{\alpha} | N!$ . Además, puesto que $\alpha_5 < \alpha_2$ la más alta potencia de $10$ dividiendo $N!$ es la mayor potencia de $5$ dividiendo $N!$ que es $\alpha_5$ .

Tenga en cuenta que habrá 

 1. Un salto de $1$ cero pasando de $(N-1)!$ a $N!$ si $5 \mathrel\| N$

 2. Un salto de $2$ ceros que van desde $(N-1)!$ a $N!$ si $5^2 \mathrel\| N$

 3. Un salto de $3$ ceros que van desde $(N-1)!$ a $N!$ si $5^3 \mathrel\| N$ y en general

 4. Un salto de $k$ ceros que van desde $(N-1)!$ a $N!$ si $5^k \mathrel\| N$

donde $a \mathrel\| b$ significa $a$ divide $b$ y $\gcd\left(a,\dfrac{b}{a} \right)$ = 1.

Mayor potencia de un primo que divide otros productos afines

En general, si queremos encontrar la mayor potencia de un primo $p$ dividiendo números como $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ , $\displaystyle P(N,r)$ , $\displaystyle \binom{N}{r}$ La clave es escribirlos en términos de factoriales.

Por ejemplo, $$\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1) = \frac{(2N)!}{2^N N!}.$$ Por lo tanto, la mayor potencia de un primo, $p>2$ dividiendo $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ viene dada por $s_p((2N)!) - s_p(N!)$ , donde $s_p(N!)$ se define más arriba. Si $p = 2$ entonces la respuesta es $s_p((2N)!) - s_p(N!) - N$ .

De la misma manera, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Por lo tanto, la mayor potencia de un primo, dividiendo $\displaystyle P(N,r)$ viene dada por $s_p(N!) - s_p((N-r)!)$ , donde $s_p(N!)$ se define más arriba.

De la misma manera, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Por lo tanto, la mayor potencia de un primo, dividiendo $\displaystyle C(N,r)$ viene dada por $$s_p(N!) - s_p(r!) - s_p((N-r)!)$$ donde $s_p(N!)$ se define más arriba.

Answer 2

Para un número $n$ , defina $\Lambda(n)=\log p$ si $n=p^k$ y cero en los demás casos.

Tenga en cuenta que $\log n=\sum\limits_{d\mid n}\Lambda(d)$ . Si $N=n!$ entonces $$\log N=\sum_{k=1}^n\log k=\sum_{k=1}^n\sum_{d\mid k}\Lambda (d)=\sum_{d=1}^n \Lambda(d)\left\lfloor \frac nd\right\rfloor$$

Desde $\Lambda(d)$ es distinto de cero precisamente cuando $d$ es una potencia de un primo y en tal caso es igual a $\log p$ la última suma es igual a $$\sum_{p}\sum_{k\geqslant 1}\log p \left\lfloor\frac n{p^k}\right\rfloor$$ y esto da $$\nu_p(n!)=\sum_{k\geqslant 1}\left\lfloor\frac n{p^k}\right\rfloor$$ Si escribe $n$ es la base $p$ , digamos que $n=a_0+a_1p+\cdots+a_kp^k$ lo anterior da como resultado que $$\nu_p(n!)=\frac{s(n)-n}{1-p}$$ donde $s(n)=a_0+\cdots+a_k$ .

Answer 3

La fórmula de Polignac que lleva el nombre de Alphonse de Polignac, da la descomposición prima del factorial $n!$ .

Answer 4

Para algo completamente diferente, véase la página 114 de Concrete Mathematics de Graham, Knuth, Patashnik. La mayor potencia de un primo $p$ dividiendo $n!$ es $n$ menos la suma de los dígitos enteros de $n$ en la base $p$ , todo ello dividido por $p-1$ . En Mathematica escribirías:

(n-Total[IntegerDigits[n,p]])/(p-1)

Por lo tanto, el número de ceros finales de $n!$ es

(n-Total[IntegerDigits[n,5]])/4

He descubierto que este método es mucho más rápido que la suma de las funciones del Piso...

Answer 5

Caminando por la calle me di cuenta de cómo probar la fórmula de una manera muy sencilla. La idea clave es saber cuántos números contienen un primo dado en el exacto $q$ - de la energía.

Denotemos el conjunto de todos los números hasta $n$ (inclusive) que son divisibles por $q$ -ésima potencia de primo $p$ pero no divisible por el mayor ( $q+1, q+2, ...$ ) potencia de ese primo: $$ M^p_q(n) := \{ m : m \le n, p^q | m, p^{q+1} \nmid m\} $$ ¿Cuántos números hay en ese conjunto? Bueno, obviamente, el número de los que son divisibles por $p^q$ menos el número de los que son divisibles por $p^{q+1}$ : $$ |M^p_q(n)| = \bigg\lfloor \frac{n}{p^q}\bigg\rfloor - \bigg\lfloor \frac{n}{p^{q+1}}\bigg\rfloor $$ BIEN. Cada uno de los números de $M^p_q$ nos da la $q$ -enésima potencia de $p$ en $n!$ así que sólo tenemos que añadirlos todos: $$ s_p(n!)=\sum_{q=1}^{\infty}q|M^p_q(n)| $$ Que es el resultado deseado.