Fórmula de Legendre
2 participantes
Página 1 de 1
Fórmula de Legendre
por Emanuel Dias Qui 03 Set 2020, 15:04
Alguém poderia me ajudar a demonstrar a fórmula de Legendre?
Para um primo p e um positivo n, seja v(p) o maior expoente de p que divide n, então:
[latex]\upsilon (p)=\sum_{i=1}^{\infty }=\left \lfloor \frac{n}{p^i} \right \rfloor[/latex]
https://proofwiki.org/wiki/De_Polignac%27s_Formula
Um exemplo de aplicação.
7!=720=[latex]2^4\cdot 3^2\cdot 5[/latex]=[latex]2^a\cdot 3^b\cdot 5^{c}[/latex]
Queremos, por exemplo, saber qual a o valor de a,
p=2
[latex]\sum _{i=1}^{\infty }=\left \lfloor \frac{n}{p^i} \right \rfloor=\left \lfloor \frac{7}{2} \right \rfloor+\left \lfloor \frac{7}{4} \right \rfloor=3+1=4[/latex]
A prova que encontrei não detalha muito não consegui deduzir, alguém sabe provar ?
Para um primo p e um positivo n, seja v(p) o maior expoente de p que divide n, então:
[latex]\upsilon (p)=\sum_{i=1}^{\infty }=\left \lfloor \frac{n}{p^i} \right \rfloor[/latex]
https://proofwiki.org/wiki/De_Polignac%27s_Formula
Um exemplo de aplicação.
7!=720=[latex]2^4\cdot 3^2\cdot 5[/latex]=[latex]2^a\cdot 3^b\cdot 5^{c}[/latex]
Queremos, por exemplo, saber qual a o valor de a,
p=2
[latex]\sum _{i=1}^{\infty }=\left \lfloor \frac{n}{p^i} \right \rfloor=\left \lfloor \frac{7}{2} \right \rfloor+\left \lfloor \frac{7}{4} \right \rfloor=3+1=4[/latex]
A prova que encontrei não detalha muito não consegui deduzir, alguém sabe provar ?
____________________________________________
El Álgebra no es más que Geometría y la Geometría no es más que Álgebra abstracta
Sophie Germain
Sophie Germain
Emanuel Dias- Monitor
- Mensagens : 1703
Data de inscrição : 15/12/2018
Idade : 22
Localização : São Paulo
Re: Fórmula de Legendre
por Robson Jr. Sex 04 Set 2020, 14:26
Emanuel, primeiro uma pequena correção no enunciado:
Para ilustrar o que está acontecendo, vamos usar um fatorial um pouco maior:
O segredo é perceber que [latex]\left \lfloor \frac{10}{2^i} \right \rfloor[/latex] representa o número de múltiplos de 2i no intervalo fechado [1, 10].
A 1ª conta igual a 5 representa os fatores 2, 4, 6, 8 e 10.
A 2ª conta igual a 2 representa os fatores 4 e 8.
A 3ª conta igual a 1 representa o fator 8.
Entendido isso, para provar a fórmula só precisamos mostrar que ela dá conta de todas potências do primo p no intervalo [1, n], ou seja, o intervalo dos inteiros que aparecem como fatores na expressão de n fatorial.
Sejam:
Naturalmente, j <= k implica pj <= n, portanto pj é um dos fatores de n fatorial.
Veja que [latex]\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor[/latex] conta exatamente as j potências de p no fator pj:
Para um primo p e um positivo n, seja v(p) o maior expoente de p que divide n!
Para ilustrar o que está acontecendo, vamos usar um fatorial um pouco maior:
[latex]10! = 10*9*8*7*6*5*4*3*2*1[/latex]
O segredo é perceber que [latex]\left \lfloor \frac{10}{2^i} \right \rfloor[/latex] representa o número de múltiplos de 2i no intervalo fechado [1, 10].
[latex]\\ \left \lfloor \frac{10}{2^1} \right \rfloor= 5 \\\\ \left \lfloor \frac{10}{2^2} \right \rfloor= 2 \\\\ \left \lfloor \frac{10}{2^3} \right \rfloor= 1 [/latex]
Por quê? Porque, se 10/4 = 2,5, então cabem 2 múltiplos de 4 no intervalo de 1 a 10.
A 1ª conta igual a 5 representa os fatores 2, 4, 6, 8 e 10.
A 2ª conta igual a 2 representa os fatores 4 e 8.
A 3ª conta igual a 1 representa o fator 8.
Entendido isso, para provar a fórmula só precisamos mostrar que ela dá conta de todas potências do primo p no intervalo [1, n], ou seja, o intervalo dos inteiros que aparecem como fatores na expressão de n fatorial.
Sejam:
- p um primo;
- k o maior inteiro positivo tal que pk <= n;
- j um inteiro arbitrário tal que 1 <= j <= k
Naturalmente, j <= k implica pj <= n, portanto pj é um dos fatores de n fatorial.
Veja que [latex]\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor[/latex] conta exatamente as j potências de p no fator pj:
[latex]\\ \text{1 vez em }\left \lfloor \frac{n}{p^1} \right \rfloor \\\\ \text{1 vez em }\left \lfloor \frac{n}{p^2} \right \rfloor \\\\ ... \\\\ \text{1 vez em }\left \lfloor \frac{n}{p^j} \right\rfloor \\\\ \text{0 vezes em }\left \lfloor \frac{n}{p^{j+1}} \right \rfloor \text{ e alem}[/latex]
Como j é arbitrário, por raciocínio análogo, a fórmula contabiliza todos os fatores em p1, p2, p3 ... até pk.
Como não deixamos nenhuma potência de p de fora, contabilizou-se todas as potências de p no intervalo [1, n].
Logo, há [latex]\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor[/latex] fatores de p em n!, de modo que [latex]p^{\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor}[/latex] é a maior potência de p que divide n fatorial.
Robson Jr.- Fera
- Mensagens : 1263
Data de inscrição : 24/06/2012
Idade : 30
Localização : Rio de Janeiro, RJ
Emanuel Dias gosta desta mensagem
Re: Fórmula de Legendre
por Emanuel Dias Sex 04 Set 2020, 14:34
Explicação perfeita Robson. A dificuldade estava em enxergar o motivo dessa função piso funcionar, as demonstrações que vi só falavam que ela funciona, mas não falavam o porque, como você explicou. Muito obrigado.
____________________________________________
El Álgebra no es más que Geometría y la Geometría no es más que Álgebra abstracta
Sophie Germain
Sophie Germain
Emanuel Dias- Monitor
- Mensagens : 1703
Data de inscrição : 15/12/2018
Idade : 22
Localização : São Paulo
Tópicos semelhantes» Símbolo de Legendre
» Como escrevo a fórmula da queda livre a partir do repouso e a fórmula do lançamento vertical para baixo?
» Íon-Fórmula
» Formula
» quantas vezes o algarismo 7
» Como escrevo a fórmula da queda livre a partir do repouso e a fórmula do lançamento vertical para baixo?
» Íon-Fórmula
» Formula
» quantas vezes o algarismo 7
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos|
|
|
