Cómo encontrar el exponente de un primo en $n!$

Question

Sea el número entero positivo $n$ se escriben como potencias de primos $p$ para que tengamos $n=a_kp^k+....+a_2p^2+a_1p+a_0,$ donde $0\leq a_i<p.$ Demuestre que el exponente de la mayor potencia de $p$ que aparece en la factorización primaria de $n!$ es $\frac{n-(a_k+....+a_1+a_0)}{p-1}$ .

Sé que el exponente de $p$ en $n!$ es $\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor$ . Pero me he atascado en cómo utilizar la expresión dada de $n$ . ¿Alguna sugerencia?

Answer 1

$$ \begin{align} \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor &= \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dotsb + \left\lfloor \frac{n}{p^k} \right\rfloor + \sum_{i=k+1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor \\ &= \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dotsb + \left\lfloor \frac{n}{p^k} \right\rfloor \\ &= \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p} \right\rfloor + \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p^2} \right\rfloor + \dotsb \\ &\phantom{= \lfloor} + \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\ &= \left\lfloor \frac{n - a_0}{p} + \frac{a_0}{p} \right\rfloor + \left\lfloor \frac{n - (a_1p + a_0)}{p^2} + \frac{a_1p + a_0}{p^2} \right\rfloor + \dotsb \\ &\phantom{= \lfloor} + \left\lfloor \frac{n - (a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0)}{p^k} + \frac{a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\ &= (a_kp^{k-1} + \dotsb + a_2p + a_1) + (a_kp^{k-2} + \dotsb + a_3p + a_2) + \dotsb + (a_k) \\ &\phantom{= \lfloor} + \left\lfloor \frac{a_0}{p} \right\rfloor + \left\lfloor \frac{a_1p + a_0}{p^2} \right\rfloor + \dotsb \left\lfloor \frac{a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\ &= (a_kp^{k-1} + \dotsb + a_2p + a_1) + (a_kp^{k-2} + \dotsb + a_3p + a_2) + \dotsb + (a_k) \\ &= p^{k-1}a_k + p^{k-2}(a_{k-1} + a_k) + \dotsb + p(a_2 + a_3 + \dotsb + a_k) + (a_1 + a_2 + \dotsb + a_k) \\ &= \frac{(p - 1)(p^{k-1}a_k + p^{k-2}(a_{k-1} + a_k) + \dotsb + p(a_2 + a_3 + \dotsb + a_k) + (a_1 + a_2 + \dotsb + a_k))}{p - 1} \\ &= \frac{a_kp^k - a_kp^{k-1} + a_{k-1}p^{k-1} + a_kp^{k-1} - \dotsb + p(a_1 + a_2 + \dotsb + a_k) - (a_1 + a_2 + \dotsb + a_k))}{p - 1} \\ &= \frac{a_kp^k + a_{k-1}p^{k-1} + \dotsb + a_0 - (a_1 + a_2 + \dotsb + a_k)}{p - 1} \\ &= \frac{n - (a_1 + a_2 + \dotsb + a_k)}{p - 1} \end{align} $$

• Línea 2: El resto de la suma es cero.
• Línea 5: La primera parte de cada paréntesis de piso es un número entero, y por lo tanto viene fuera de los paréntesis.
• Línea 6: Las fracciones dentro de los paréntesis son menores que uno debido a la forma $n$ y $a_0, a_1, \dotsc, a_k$ están definidos.
• Línea 10: La cancelación funciona algo así como una suma telescópica, cancelando todos los términos excepto los de la línea siguiente. (Esto puede verificarse).

Answer 2

Aplicando la fórmula de Legendre, la primera división da como resultado

$$a_kp^{k-1}+a_{k-1}p^{k-2}+\cdots a_2p+a_1,$$ el siguiente $$a_kp^{k-2}+a_{k-1}p^{k-3}+\cdots a_2,$$ y así sucesivamente hasta $$a_k.$$

Sumando esos términos verticalmente, obtenemos con la fórmula de la serie geométrica

$$a_k\frac{p^k-1}{p-1}+a_{k-1}\frac{p^{k-1}-1}{p-1}+\cdots a_2\frac{p^2-1}{p-1}+a_1=\frac{a_kp^k+a_{k-1}p^{k-1}+\cdots a_2p^2+a_1p+a_0-a_k-a_{k-1}-\cdots a_1-a_0}{p-1}.$$