(
ponto) Existe um inteiro
divisível por exatamente 2000 primos diferentes e tal que
divide
?
Passo 1
O enunciado pergunta se existe um inteiro
tal que:
-
seja divisível por exatamente primos distintos (ou seja, o número de fatores primos distintos de é ); - e ao mesmo tempo
divida , isto é,
Informações relevantes dadas pelo enunciado (resumidas):
- Queremos um
com exatamente primos distintos. - Queremos também que cada primo que divide
divida , de modo que o produto desses primos (ou seja, ) divida .
Passo 2
Ideia geral que vamos usar (explicada devagar):
- Vamos construir
como produto de primos distintos . - A construção será recursiva: em cada passo escolhemos um primo novo
que divide , onde é o produto dos primos já escolhidos antes do passo . - Depois de escolher
definimos . Assim tem um primo novo na sua fatoração. - Precisamos de duas propriedades para que isso funcione:
- Em cada passo exista pelo menos um primo novo
que divide e que não apareça entre os primos escolhidos anteriormente. - Se um primo
divide e é um inteiro ímpar, então também divide . Essa última propriedade garante que, uma vez que um primo divide , ele continuará dividindo todos os para , desde que os quocientes sejam ímpares (o que acontecerá na nossa construção porque multiplicamos por primos ímpares).
- Em cada passo exista pelo menos um primo novo
Agora vou explicar e justificar com calma esses dois pontos.
Passo 3
Explicando e justificando a propriedade "se
e
é ímpar então
":
- Seja
. Se , então . - Se
é ímpar, então . Logo . - Mas
. Portanto . - Conclusão: sempre que um primo divide
, ele também divide para todo ímpar.
Essa propriedade será usada frequentemente na construção para propagar divisibilidades quando multiplicamos o expoente por um primo ímpar.
Passo 4
Sobre a existência de um primo “novo” em cada passo (no jargão: existência de um divisor primo primitivo de
):
- Há um resultado clássico (Zsigmondy, versão prática) que diz, em termos simples: para inteiros
e existem, com poucas exceções, divisores primos de que não dividem para nenhum divisor próprio de . Adaptando ao nosso caso e escrevendo (que está ligado a ), obtemos que para todo \emph{ímpar} existe um primo que divide mas não divide para nenhum divisor próprio de , com a exceção conhecida de (pois não traz primo novo). - Na linguagem mais elementar: para
ímpar e sempre há um primo divisor de que é “novo”, isto é, não aparece como divisor de para divisores . - Não precisa saber a demonstração completa de Zsigmondy agora; basta saber que essa afirmação é um teorema padrão e nos dá exatamente o “primo novo” que precisamos em cada etapa, desde que o expoente do passo seja ímpar e diferente de
.
Passo 5
Construção explícita passo a passo (indutiva), evitando as exceções:
- Começamos escolhendo um inteiro inicial
ímpar com e . Por simplicidade tomamos (porque tem o primo novo ). - Pelo argumento do passo anterior (Zsigmondy para
) existe um primo que divide e que não divide para nenhum divisor próprio de . Podemos escolher . - Definimos
. Observe que é ímpar e maior que , e não é igual a . - Em geral, suponha que em algum passo
já temos um inteiro que é produto de primos distintos , todos ímpares, com e . (Isto é verdade para com .) - Então, aplicando novamente o resultado (Zsigmondy) a
(já que é ímpar e ), existe um primo que divide e que não divide para nenhum divisor próprio de . Esse é um primo novo (não coincide com nenhum ). - Definimos
. Assim tem exatamente primos distintos na sua fatoração.
Passo 6
Mostrando que cada
divide
(a propriedade que queremos):
- Vamos provar por indução que, para cada
, todos os primos dividem . Logo o produto divide (porque fatores são primos distintos, portanto coprimos entre si, e se cada um divide o número então o produto divide). - Base
: por construção divide . - Passo indutivo: suponha que para
já sabemos que dividem . Ao escolher nós tomamos um primo que divide . Agora e o quociente é ímpar, portanto, pelo argumento do Passo 3, qualquer primo que divide também divide . Assim dividem . Isso conclui a indução. - Consequência: para cada
o número divide .
Passo 7
Concluindo para
primos:
- Repetindo o passo anterior
vezes (começando em e aplicando o procedimento descrito), obtemos um inteiro que é produto de primos distintos e que satisfaz - Portanto tomando
temos exatamente o que o enunciado pede: é divisível por exatamente primos diferentes e .
Passo 8
Observações finais e verificação das hipóteses usadas:
- É importante que em cada etapa o expoente seja ímpar e diferente de
para escapar da exceção onde não surge primo novo. Começamos em , e a cada passo multiplicamos por primos ímpares, então todos os permanecem ímpares e nunca igualam . - O uso do teorema de Zsigmondy (na forma prática que garante um divisor primo primitivo para
quando é ímpar e ) é o ingrediente que garante a existência do primo novo em cada passo. Esse é um resultado padrão em teoria dos números; a construção que dei é a forma canônica de obter inteiros com arbitrariamente muitos primos distintos que satisfazem . - Assim, não só existe um
com a propriedade pedida, como existe um método explícito para construir um com qualquer número desejado de primos distintos (neste caso, ).
Resposta
Sim.