quarta-feira, 9 de maio de 2012

040-Expoente de Primo em Fatoração de Fatorial

No enunciado a seguir, [;[u];] significa a parte inteira de [;u;], com [;u \geq 0;] real.

Teorema. Sejam [;p;], [;n;] e [;r;] inteiros positivos, com [;p;] primo, de forma que [;1<p\leq n;] e [;r=[log_pn];] é o maior expoente de [;p;] na desigualdade [;p^r\leq;][;n;].

Então o expoente de [;p;] na fatoração de [;n!;] é


Exemplo [;1;]. Calcular o expoente de [;3;] na fatoração de [;9!;]. Observem que não só calcular o fatorial de [;9!;] quanto fatorar [;9!=362880;] é algo trabalhoso. O teorema acima permite um atalho para resolver o problema proposto. Veja,

[;E_3(9!)=[9/3]+[9/3^2]=[3]+[1]=3+1=4;]

De fato, pois [;9!=2^7.3^4.5.7;] ( o expoente de [;3;] é [;4;] ).

Exemplo [;2;] . Calcular o expoente de [;5;] na fatoração de [;138!;].

[;E_5(138!)=[138/5]+[138/25]+[138/125]=[27]+[5,52]+[1,104]=27+5+1=33;]

Observem que, como [;5^4=625>138;], paramos de somar os valores entre colchetes quando o último denominador foi [;5^3=125 \leq 138;].

DEMONSTRAÇÃO 

Os múltiplos de [;p\leq n;], são [;p;],[;2p;],[;3p;],...,[;kp;], com [;kp \leq n;] e [;k;] máximo. Assim, se dividirmos [;n;] por [;p;] vamos ter o quociente [;k;] com resto ou não. Portanto, [;k;] é a parte inteira de [;n/p;], ou seja, [;k=[n/p];].

Dentro de [;n!;]  vamos ter o produto [;P=(p)(2p)(3p)...(kp)=p^k.k!;], com [;k=[n/p];].

Concluimos então que o expoente de [;p;] na fatoração de [;n!;] é o mesmo expoente de [;p;] na fatoração de [;P;].

No entanto, o expoente total de [;p;] em [;P=p^k.k!;] é [;k;][;+;] (expoente de [;p;] na fatoração de [;k!;] ).

Pela mesma lógica, o expoente de [;p;] na fatoração de [;k!;] é o mesmo expoente de [;p;] na fatoração de [;P^'=p^k^'.k^'!;], com [;k^'=[k/p]=[[n/p]/p]=[n/p^2];].

E o  o expoente de [;p;] na fatoração de [;k^';] é o mesmo expoente de [;p;] na fatoração de [;P^{''}=p^k^{''}.k^{''}!;], com [;k^{"}=[k^'/p]=[[n/p^2]/p]=[n/p^3];].

Etc, de forma que, se [;p^{r+1}>n;], teremos [;[n/p^{r+1}]=0;] e paramos o processo com [;p^r \leq n;], antes que  a primeira desigualdade seja atingida. Assim, se [;r;] é o máximo valor inteiro tal que [;p^r \leq n;], isto implica em [;r=[log_pn];]. Mas vejam pelos exemplos [;1;] e [;2;] que não é necessário calcular este logaritmo.

O que fizemos foi encontrar expoentes parciais de [;p;] na fatoração de [;n!;] . Sendo [;E_p(n!);] o expoente de [;p;] na fatoração de [;n!;], temos

[;p^{E_p(n!)}=p^k.p^k^{'}.p^k^{''}...p^{k_{r}}=p^{[n/p]}.p^{[n/p^2]}p^{[n/p^3]}...p^{[n/p^r]} \Rightarrow;]

[;E_p(n!)=[n/p]+[n/p^2]+[n/p^3]+...+[n/p^r] ;] ,

com [;r=[log_pn];]

Referência Bibliográfica

Funções Aritméticas  - Números Notáveis, de Edgard de Alencar Filho, Editora Nobel,1988




5 comentários:

  1. Muito interessante este teorema. Acho que através dele é possível responder a pergunta: Quantos zeros termina n!?

    ResponderExcluir
  2. Oi, Teixeira e Prof Paulo! Bem lembrado, Professor! A quantidade de "cincos"(5) será a quantidade de "zeros". Vi também, há muito tempo, esse teorema sendo usado na demonstração de que (e^2) é irracional, o autor usava-o para cancelar os "2" que apareciam no numerador e no denominador do termo geral da série que define (e^2). Termo geral=(2^n)/n!, infelizmente não lembro detalhes. Obrigado..abçs

    ResponderExcluir
  3. Oi, amigos!

    Paulo, essa questão sobre os zeros terminais de [;n!;] é clássica para este teorema e acabei esquecendo de evidenciar isto.

    Mas em um futuro post, além da questão dos zeros, mostrarei também que se [;a_0,a_1,...,a_z;] são os dígitos de [;n;] na base [;b;], então


    [;E_n(n!)=\frac{n-\sum_{i=0}^{i=z}a_i}{p-1};]

    Tavano, nada como compartilhar conhecimentos pois o que sei é [;0,...1;] por cento do que as outras pessoas sabem. Essa questão do [;e^2;] é novidade para mim.

    Abraços!

    ResponderExcluir
  4. Olá Teixeira,

    Houve um "cochilo" na digitação:

    Em vez de 9! = 332880, deveria ser 9! = 362880

    Em vez de E5(139!), deveria ser: E5(138!)

    Abraços

    Sebá

    ResponderExcluir