Fatorial: diferenças entre revisões

2 163 bytes removidos ,  17h52min de 27 de maio de 2016
m
Foram revertidas as edições de 177.220.157.245 para a última revisão de Mjunii, de 16h08min de 25 de maio de 2016 (UTC)
m (Foram revertidas as edições de 177.220.157.245 para a última revisão de Mjunii, de 16h08min de 25 de maio de 2016 (UTC))
 
O [[Teorema de Wilson]] diz que ''(p-1)! + 1'' é um múltiplo de ''p'' se, e somente se, ''p'' for um [[número primo]].
===Um método alternativo===
É possível calcular o expoente de um número primo <math>p</math> na decomposição de <math>n!</math> escrevendo-se o número <math>n</math> como a soma das potências de <math>p</math> (de modo semelhante ao usado na [[Conversão entre sistemas numéricos]]), e depois substitui-se cada uma dessas potências pelo somatório de todas as potências menores de <math>p</math>, incluindo-se <math>p^0=1</math> e calcula-se o resultado.
Vejamos alguns exemplos para melhor clareza:
 
1) Qual é o expoente de 2 na fatoração prima de <math>14!</math>?
 
<math>14=8+4+2={\color{blue}2^3}+{\color{blue}2^2}+{\color{blue}2}</math>.
 
Substituindo-se <math>2^3</math> por <math>(1+2^1+2^2)=7</math>,
 
e depois <math>2^2</math> por <math>(1+2^1)=3</math> e
 
<math>2^1</math> por <math>1</math> (pois é igual a <math>2^0</math>) e calculando, obtemos:
 
<math>7+3+1=11</math>. Logo <math>14!</math> é múltiplo de <math>2^{11}</math> na sua decomposição em fatores primos.
 
Outro exemplo:
 
2) Se <math>n!</math> em sua fatoração prima é múltiplo de <math>5^{2016}</math>, determine o menor valor possível de <math>n</math>.
 
O caminho é o inverso: escreve-se 2016 como a soma dos somatórios de potências de 5 (dados pela tabela abaixo) e depois substitui-se cada um desses somatórios pela menor potência de 5 que é maior que o somatório.
 
{| border="2" cellpadding="2"
! n
! <math>5^n</math>
! <math>\sum_{k=0}^{n-1}5^k</math>
|-
| 0 || 1 || <math>-</math>
|-
| 1 || 5 || 1
|-
| 2 || 25 || 6
|-
| 3 || 125 || 31
|-
| 4 || 625 || 156
|-
| 5 || 3125 || 781
|-
| <math>\cdots</math>
| <math>\cdots</math>
| <math>\cdots</math>
|}
 
Então temos:
 
<math>2016=2\cdot{\color{blue}781}+2\cdot{\color{blue}156}+4\cdot{\color{blue}31}+3\cdot{\color{blue}6}</math>
 
Substituindo-se os números em azul pelas potências de 5 correspondentes na tabela acima e calculando-se, vem:
<math>{\color{red}3125}\cdot2+{\color{red}625}\cdot2+{\color{red}125}\cdot4+{\color{red}25}\cdot3=2\cdot5^5+2\cdot5^4+4\cdot5^3+3\cdot5^2=8075</math>.
 
O que significa que <math>8075!</math> em sua fatoração prima é múltiplo de <math>5^{2016}</math>.
 
== Algoritmo ==