(PUC-SP) Considere o número inteiro
produto de 101 números inteiros sucessivos. Ao escrever-se P como um produto de fatores primos, o número de vezes que o fator 7 aparece é
(a) 15
(b) 16
(c) 17
(d) 18
(e) 19
(a) 15
(b) 16
(c) 17
(d) 18
(e) 19
Passo 1
O enunciado dá o número inteiro
produto de todos os inteiros consecutivos de
até
(inclusive). A pergunta é: ao escrever
como produto de fatores primos, qual é o número de vezes que o fator primo
aparece? Ou seja, calcular o expoente de
na fatoração prima de
.
Informações relevantes:
- O produto contém todos os inteiros
tais que . - Para contar o número de vezes que um primo
aparece numa multiplicação de inteiros consecutivos usamos a contagem de múltiplos de no intervalo.
Passo 2
Ideia e fórmula que vamos usar (explicação didática):
- Se a gente quer saber quantas vezes o primo
aparece em , existe a fórmula de Legendre:
onde
é o expoente de
na fatoração. Isso funciona porque
conta quantos números até
são múltiplos de
(cada um contribui com pelo menos um
),
conta quantos são múltiplos de
(cada um desses tem um
extra), e assim por diante.
- Nosso produto é de um intervalo
. Podemos relacionar com fatoriais:
Logo o expoente de
em
é
Isto dá o número de múltiplos de
em
somados com multiplicidade apropriada.
Exemplo simples para entender: se o intervalo fosse
e quiséssemos contar fatores
, então múltiplos de
são
(2 ocorrências) e múltiplos de
é
(contribui com mais um
), total
fatores
. A mesma ideia generaliza aqui.
Passo 3
Aplicando para
: contamos múltiplos de
no intervalo
.
Usamos a diferença de pisos:
Usamos a diferença de pisos:
Calculemos cada piso:
Portanto o número de múltiplos de
em
é
(Verificação alternativa: o primeiro múltiplo de
maior ou igual a
é
e o último é
. Contando de
a
dá
.)
Passo 4
Agora contamos múltiplos de
no mesmo intervalo — esses dão um
extra cada um (pois são divisíveis por
):
Calculemos:
Logo há
números em
divisíveis por
. Esses dois números são
e
. Cada um contém pelo menos
, por isso já contabilizamos um
para eles na conta dos múltiplos de
e precisamos somar mais um por cada um (o que fazemos aqui).
Passo 5
Verificamos potências maiores:
, portanto não há múltiplos de
no intervalo. Assim não há contribuições adicionais.
Passo 6
Somando as contribuições:
- múltiplos de
: , - múltiplos de
(extra): , - maiores potências:
.
Portanto o expoente de
em
é
Resposta
(b) 16