Autor Tema: Máxima potencia de \(p\) primo dividiendo a \((p^n)!\)

0 Usuarios y 1 Visitante están viendo este tema.

28 Febrero, 2024, 04:28 am
Leído 1666 veces

Dark

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 426
  • País: 00
  • Karma: +0/-0
  • Sexo: Masculino
Quiero calcular la maxima potencia de $$p$$ que divida a $$(p^{n})!$$, donde $$p$$ es primo y $$n\in\mathbb N$$.

$$(p^n)!=p^n(p^n-1)(p^n-2)\cdots (p^n-(p^n-1))$$, el factor $$p^n$$ es divisible por $$p$$ pero creo que los demás factores no, si tomamos $$p^n-1=(p-1)(p^{n-1}+p^{n-2}+\cdots+p+1)$$ vemos que los dos factores no son divisibles por $$p$$.

Entonces, creería que la maxima potencia es $$p^n$$.

28 Febrero, 2024, 04:38 am
Respuesta #1

Juan Pablo Sancho

  • Moderador Global
  • Mensajes: 6,562
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Tienes que \( 2^7 | (2^3)! \) , esto sucede por que pueda ser que \( p^n - k = m \cdot p \)

28 Febrero, 2024, 06:53 am
Respuesta #2

Richard R Richard

  • Ingeniero Industrial
  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,062
  • País: ar
  • Karma: +2/-0
  • Sexo: Masculino
  • Dentro de la ciencia todo,fuera de la ciencia nada
Dentro del factorial de $$p^n$$ se incluye a parte del propio $$p^n$$ que tiene potencia $$n$$, los factores $$p^{n-1}, p^{n-2},...,p$$  así el maximo exponente  de $$p$$ que lo divide exactamente

$$N=\sum\limits_{i=1}^{n} p^{i-1}$$

Saludos  \(\mathbb {R}^3\)

28 Febrero, 2024, 08:10 am
Respuesta #3

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Quiero calcular la maxima potencia de $$p$$ que divida a $$(p^{n})!$$, donde $$p$$ es primo y $$n\in\mathbb N$$.

$$(p^n)!=p^n(p^n-1)(p^n-2)\cdots (p^n-(p^n-1))$$, el factor $$p^n$$ es divisible por $$p$$ pero creo que los demás factores no, si tomamos $$p^n-1=(p-1)(p^{n-1}+p^{n-2}+\cdots+p+1)$$ vemos que los dos factores no son divisibles por $$p$$.

Entonces, creería que la maxima potencia es $$p^n$$.

Los múltiplos de \( p \) menores que \( p^n \) son de la forma \( p^k\cdot j \) para \( j\in\{1,\ldots,p-1\} \) y \( k\in\{1,\ldots,n-1\} \), y observa que son todos distintos entre sí, debido al teorema de factorización única de los naturales, por tanto la máxima potencia de \( p \) que divide a \( (p^n)! \) es \( C=n+\sum_{k=1}^{n-1}k(p-1)=n+\tfrac1{2}(p-1)n(n-1) \).

Corrección: ni caso a lo de arriba, está mal.

28 Febrero, 2024, 08:55 am
Respuesta #4

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 12,032
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Quiero calcular la maxima potencia de $$p$$ que divida a $$(p^{n})!$$, donde $$p$$ es primo y $$n\in\mathbb N$$.

$$(p^n)!=p^n(p^n-1)(p^n-2)\cdots (p^n-(p^n-1))$$, el factor $$p^n$$ es divisible por $$p$$ pero creo que los demás factores no, si tomamos $$p^n-1=(p-1)(p^{n-1}+p^{n-2}+\cdots+p+1)$$ vemos que los dos factores no son divisibles por $$p$$.

Entonces, creería que la maxima potencia es $$p^n$$.

No. Piensa en el producto de tres números pares, por ejemplo, 2,4,14, su descomposición es \( 2^{1}\cdot2^{2}\cdot2\cdot7 \), que es divisible por \( 2^{4} \). Entonces, si consideraras, por ejemplo, \( (2^4)! \), ocurre que además del 16, entrarían, entre otros pares, ésos de ahí, el 2, el 4 y el 14.

Por tanto, con esto ves que tienes que considerar todos los múltiplos de \( p^{1} \), de \( p^{2} \)... hasta \( p^{n} \), y no sólo las potencias puras de “p”.

Mejor dicho así: todos los múltiplos de \( p^{n} \), de \( p^{n-1} \)... hasta los que son sólo de “p”; porque los de \( p^{2} \) también son múltiplos de \( p^{1} \), etc., y se podría entender mal lo que quería decir.

Saludos.


28 Febrero, 2024, 09:39 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Los múltiplos de \( p \) menores que \( p^n \) son de la forma \( p^k\cdot j \) para \( j\in\{1,\ldots,p-1\} \) y \( k\in\{1,\ldots,n-1\} \), y observa que son todos distintos entre sí, debido al teorema de factorización única de los naturales, por tanto la máxima potencia de \( p \) que divide a \( (p^n)! \) es \( C=n+\sum_{k=1}^{n-1}k(p-1)=n+\tfrac1{2}(p-1)n(n-1) \).

Ojo. Eso no es cierto, por ejemplo \( 2^1\cdot 11 \) es menor que \( 2^{10} \).

La fórmula correcta es la que ha dado Richard R Richard:

Dentro del factorial de $$p^n$$ se incluye a parte del propio $$p^n$$ que tiene potencia $$n$$, los factores $$p^{n-1}, p^{n-2},...,p$$  así el maximo exponente  de $$p$$ que lo divide exactamente

$$N=\sum\limits_{i=1}^{n} p^{i-1}$$

aunque reconozco que no entiendo muy bien como lo deduce.

Yo razono así:

- Los múltiplos de \( p \) menores o iguales que \( p^n \) son de la forma \( p\cdot k_1 \) con \( 1\leq k_1\leq p^{n-1} \). Hay por tanto \( p^{n-1} \) de ellos que contribuyen cada uno en una unidad al exponente máximo de \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^2 \) aquellos en que \( k_1=p\cdot k_2 \) con \( 1\leq k_2\leq p^{n-2} \). Por tanto hay \( p^{n-2} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^3 \) aquellos en que \( k_2=p\cdot k_3 \) con \( 1\leq k_3\leq p^{n-3} \). Por tanto hay \( p^{n-3} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).

y así sucesivamente. Por tanto la potencia máxima es:

\( p^{n-1}+p^{n-2}+\ldots+1=\dfrac{p^n-1}{p-1} \)

Saludos.

28 Febrero, 2024, 09:42 am
Respuesta #6

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Hola

Los múltiplos de \( p \) menores que \( p^n \) son de la forma \( p^k\cdot j \) para \( j\in\{1,\ldots,p-1\} \) y \( k\in\{1,\ldots,n-1\} \), y observa que son todos distintos entre sí, debido al teorema de factorización única de los naturales, por tanto la máxima potencia de \( p \) que divide a \( (p^n)! \) es \( C=n+\sum_{k=1}^{n-1}k(p-1)=n+\tfrac1{2}(p-1)n(n-1) \).

Ojo. Eso no es cierto, por ejemplo \( 2^1\cdot 11 \) es menor que \( 2^{10} \).

Uy, cierto.

28 Febrero, 2024, 10:36 am
Respuesta #7

Richard R Richard

  • Ingeniero Industrial
  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,062
  • País: ar
  • Karma: +2/-0
  • Sexo: Masculino
  • Dentro de la ciencia todo,fuera de la ciencia nada

La fórmula correcta es la que ha dado Richard R Richard:


Dentro del factorial de $$p^n$$ se incluye a parte del propio $$p^n$$ que tiene potencia $$n$$, los factores $$p^{n-1}, p^{n-2},...,p$$  así el maximo exponente  de $$p$$ que lo divide exactamente

$$N=\sum\limits_{i=1}^{n} p^{i-1}$$


aunque reconozco que no entiendo muy bien como lo deduce.

Yo razono así:

- Los múltiplos de \( p \) menores o iguales que \( p^n \) son de la forma \( p\cdot k_1 \) con \( 1\leq k_1\leq p^{n-1} \). Hay por tanto \( p^{n-1} \) de ellos que contribuyen cada uno en una unidad al exponente máximo de \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^2 \) aquellos en que \( k_1=p\cdot k_2 \) con \( 1\leq k_2\leq p^{n-2} \). Por tanto hay \( p^{n-2} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^3 \) aquellos en que \( k_2=p\cdot k_3 \) con \( 1\leq k_3\leq p^{n-3} \). Por tanto hay \( p^{n-3} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).

y así sucesivamente. Por tanto la potencia máxima es:

Coincido en todo de manera muy similar lo deduje yo también.

Primero posteé el sumatorio que lleva a $$n(n-1)/2$$ pero de inmediato  me di cuenta que había más potencias.

Pero escribirlo así

Citar
\( p^{n-1}+p^{n-2}+\ldots+1=\dfrac{p^n-1}{p-1} \)

No me hubiese dado cuenta ni en dos vidas, hasta que lo volví a ver escrito.
Saludos  \(\mathbb {R}^3\)

28 Febrero, 2024, 10:43 pm
Respuesta #8

Lurtz

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 1
  • País: es
  • Karma: +0/-0
Hola a todos.
- Los múltiplos de \( p \) menores o iguales que \( p^n \) son de la forma \( p\cdot k_1 \) con \( 1\leq k_1\leq p^{n-1} \). Hay por tanto \( p^{n-1} \) de ellos que contribuyen cada uno en una unidad al exponente máximo de \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^2 \) aquellos en que \( k_1=p\cdot k_2 \) con \( 1\leq k_2\leq p^{n-2} \). Por tanto hay \( p^{n-2} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^3 \) aquellos en que \( k_2=p\cdot k_3 \) con \( 1\leq k_3\leq p^{n-3} \). Por tanto hay \( p^{n-3} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).

y así sucesivamente. Por tanto la potencia máxima es:

\( p^{n-1}+p^{n-2}+\ldots+1=\dfrac{p^n-1}{p-1} \)


Siguiendo la línea de este razonamiento, conseguí verlo casi del todo claro si empezaba por 'el final': \[ p^n! \] es un número, pero da una lista de factores según la definición recursiva de factorial. La clave está en encontrar cuál es la cantidad total de factores del tipo \[ p^k \] dentro de cada uno de estos elementos; recogerlos todos en una lista y multiplicarlos: esto da la mayor potencia de \[ p \] dentro de \[ p^n! \]. Pero está el inconveniente de que un factor que sea por ejemplo del tipo \[ p^2\cdot b \] puede ser considerado también de tipo \[ p\cdot a\], si \[ a = p\cdot b\] o de tipo \[ p^3\cdot c\], si tuviéramos la mala suerte de que \[ b \] fuera múltiplo de \[ p\]. Por esta razón, es imprescindible saber qué factorizaciones son exactamente de la forma \[p\cdot a\], \[p^2 \cdot b\], \[p^3\cdot c\], etc, donde los factores \[p\], \[p^2\], \[p^3\],\[\,\ldots\] aparecen sólo una vez. Que no haya más potencias de \[p\] escondidas, sino que sean exactamente esas. Empezando por 'el final', la potencia \[ p^n \] aparece sólo 1 vez. La potencia \[ p^{n-1} \] aparece p veces, pero hay que restar 1 correspondiente a la factorización \[p^n\]. Y así sucesivamente. Esto da lugar a la lista de las veces que aparece cada potencia de \[p\] (de por entero contenida en algún factor de la factorización de \[p^n!\] según la definición recursiva clásica):

\[p^n: 1\]
\[p^{n-1}: p - 1\]
\[p^{n-2}: p^2 - (p-1) -1\]
\[p^{n-3}: p^3 - (p^2 - (p-1) -1) - (p-1) -1\]
\[\vdots\]
Y nos damos cuenta de que las sumas son telescópicas, y el resultado es:

\[p^n: 1\] veces
\[p^{n-1}: p-1\] veces
\[p^{n-2}: p^2-p\]
\[p^{n-3}: p^3-p^2\]
\[\vdots\]
\[p^{n-k}: p^k - p^{k-1}\]
\[\vdots\]
\[p^3: p^{n-3}-p^{n-4}\]
\[p^2: p^{n-2}-p^{n-3}\]
\[p^1: p^{n-1}-p^{n-2}\]
Llegados aquí se para de contar.
La cantidad de factores que presentan exactamente la potencia \[ p^k \] dentro de alguno de ellos es la dada por la lista anterior. El producto de todos es el siguiente: (donde \[  {\scriptstyle\sum} \] son coeficientes distintos pero que no vienen al caso)

\[ p^n \cdot
{\scriptstyle\sum} \cdot (p^{n-1})^{p-1} \cdot
{\scriptstyle\sum} \cdot (p^{n-2})^{p^2-p}\cdot
{\scriptstyle\sum} \cdot (p^{n-3})^{p^3-p^2}\cdot
\ldots \cdot
{\scriptstyle\sum}\cdot (p^{n-k})^{p^k-p^{k-1}}\cdot
\ldots \cdot
{\scriptstyle\sum} \cdot (p^3)^{p^{n-3}-p^{n-4}}\cdot
{\scriptstyle\sum} \cdot (p^2)^{p^{n-2}-p^{n-3}}\cdot
{\scriptstyle\sum} \cdot (p^1)^{p^{n-1}-p^{n-2}}\]

La suma finita de los exponentes puede escribirse como: \[ n + \sum_{k=1}^{n-1}k\cdot (p^{n-k}-p^{n-k-1}) \]
Se comprueba desarrollando que es telescópica,

\[1\cdot (p^{n-1}-p^{n-2})\]
\[2\cdot (p^{n-2}-p^{n-3})\]
\[3\cdot (p^{n-3}-p^{n-4})\]
\[\vdots\]
\[(n-3)(p^3-p^2)\]
\[(n-2)(p^2-p^1)\]
\[(n-1)(p^1-p^0)\]
\[n\]
Y que efectivamente el resultado es \[p^{n-1} + p^{n-2} + p^{n-3} + p^{n-4} + \ldots + p^3 + p^2 + p + 1\]         ...

Por lo que la mayor potencia de \[p\] que divide a \[ p^n!\] es \[p\] elevado a \[{\dfrac{p^n-1}{p-1}} \]    (q.e.d)

29 Febrero, 2024, 12:39 pm
Respuesta #9

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 12,032
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola a todos.
- Los múltiplos de \( p \) menores o iguales que \( p^n \) son de la forma \( p\cdot k_1 \) con \( 1\leq k_1\leq p^{n-1} \). Hay por tanto \( p^{n-1} \) de ellos que contribuyen cada uno en una unidad al exponente máximo de \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^2 \) aquellos en que \( k_1=p\cdot k_2 \) con \( 1\leq k_2\leq p^{n-2} \). Por tanto hay \( p^{n-2} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).
- Pero entre los anteriores también hay múltiplos de \( p^3 \) aquellos en que \( k_2=p\cdot k_3 \) con \( 1\leq k_3\leq p^{n-3} \). Por tanto hay \( p^{n-3} \) de ellos que además de la unidad que contabilizamos antes, contribuyen en otra unidad al exponente máximo de  \( p \).

y así sucesivamente. Por tanto la potencia máxima es:

\( p^{n-1}+p^{n-2}+\ldots+1=\dfrac{p^n-1}{p-1} \)


Siguiendo la línea de este razonamiento, conseguí verlo casi del todo claro si empezaba por 'el final':

El razonamiento es ingenioso pero eso no implica que sea complicado de entender; yo lo veo claro con la explicación que ha dado, me parece suficiente. Basta con ir analizándolo despacio lo qué quiere decir párrafo a párrafo:

Los múltiplos de \( p \) incluyen al propio \( p \), el cual podemos escribir así \( p=k_{1}p \), con k1=1.

Considerando \( k_{1} \) genérico, como una variable que engloba distintos números, su mayor valor posible lo toma en \( p^{n}=k_{1}p \), con \( k_{1}=p^{n-1} \). De esta forma habrá al menos \( p^{n-1} \) múltiplos de “p” ("múltiplos" no es la palabra, unidades de potencia)

Pero así no contamos todos, pues algunos de estos \( k_{1} \) serán también múltiplos de \( p \), y entonces los podemos escribir así, \( k_{1}=pk_{2} \), donde no hemos contado estos \( k_{1} \) aisladamente, sino sólo sus productos por “p”.

Análogamente a lo anterior, los \( k_2 \) tienen que estar entre 1 y \( p^{n-2} \), porque ya tenemos un “p” metido. luego habrá una cantidad \( p^{n-2} \) de ellos que tampoco hemos contado (Aquí lo mismo, unidades de potencia es lo que contamos, vamos contando los \( {\color{blue}p}^{{\color{blue}1}}k_{i} \) que engloban los múltiplos desde 1 hasta \( p^{n-i} \), pero al escribir sobre la marcha uso palabras que no reflejan lo que tengo en la cabeza, perdón)

Y así, repitiendo la idea, habrá algunos \( k_2 \) múltiplos de “p”. Luego, se vuelve a hacer el mismo planteamiento. Entonces aparecen unos \( k_3 \) en una cantidad de \( p^{n-3} \), etc.

Y así hasta llegar a \( p^{n-n}=1 \).

Se suman todos y ya está.

Saludos.