( \mathbf{1 , 0} ponto) Existe um inteiro N divisível por exatamente 2000 primos diferentes e tal que N divide 2^{N}+1 ?

Passo 1

O enunciado pergunta se existe um inteiro N tal que:
  • N seja divisível por exatamente 2000 primos distintos (ou seja, o número de fatores primos distintos de N é 2000);
  • e ao mesmo tempo N divida 2^{N}+1, isto é, \;N \mid 2^{N}+1.
Informações relevantes dadas pelo enunciado (resumidas):
  • Queremos um N com exatamente 2000 primos distintos.
  • Queremos também que cada primo que divide N divida 2^{N}+1, de modo que o produto desses primos (ou seja, N) divida 2^{N}+1.

Passo 2

Ideia geral que vamos usar (explicada devagar):
  • Vamos construir N como produto de 2000 primos distintos p_{1},p_{2},\dots,p_{2000}.
  • A construção será recursiva: em cada passo escolhemos um primo novo p_{k} que divide 2^{m_{k}}+1, onde m_{k} é o produto dos primos já escolhidos antes do passo k.
  • Depois de escolher p_{k} definimos m_{k+1}=m_{k}\cdot p_{k}. Assim m_{k+1} tem um primo novo p_{k} na sua fatoração.
  • Precisamos de duas propriedades para que isso funcione:
    1. Em cada passo exista pelo menos um primo novo p_{k} que divide 2^{m_{k}}+1 e que não apareça entre os primos escolhidos anteriormente.
    2. Se um primo p divide 2^{m}+1 e t é um inteiro ímpar, então p também divide 2^{m t}+1. Essa última propriedade garante que, uma vez que um primo p_j divide 2^{m_j}+1, ele continuará dividindo todos os 2^{m_k}+1 para k>j, desde que os quocientes m_k/m_j sejam ímpares (o que acontecerá na nossa construção porque multiplicamos por primos ímpares).
Agora vou explicar e justificar com calma esses dois pontos.

Passo 3

Explicando e justificando a propriedade "se p\mid 2^{m}+1 e t é ímpar então p\mid 2^{m t}+1":
  • Seja a=2^{m}. Se p\mid a+1, então a\equiv -1\pmod p.
  • Se t é ímpar, então a^{t}\equiv (-1)^{t}\equiv -1\pmod p. Logo a^{t}+1\equiv 0\pmod p.
  • Mas a^{t}=2^{m t}. Portanto p\mid 2^{m t}+1.
  • Conclusão: sempre que um primo divide 2^{m}+1, ele também divide 2^{m t}+1 para todo t í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 2^{m}+1):
  • Há um resultado clássico (Zsigmondy, versão prática) que diz, em termos simples: para inteiros a>b>0 e n>1 existem, com poucas exceções, divisores primos de a^{n}-b^{n} que não dividem a^{d}-b^{d} para nenhum divisor próprio d de n. Adaptando ao nosso caso a=2,\;b=1 e escrevendo 2^{n}+1 (que está ligado a 2^{2n}-1), obtemos que para todo \emph{ímpar} n>1 existe um primo q que divide 2^{n}+1 mas não divide 2^{d}+1 para nenhum divisor próprio d de n, com a exceção conhecida de n=3 (pois 2^{3}+1=9=3^{2} não traz primo novo).
  • Na linguagem mais elementar: para n ímpar e n\neq 3 sempre há um primo divisor de 2^{n}+1 que é “novo”, isto é, não aparece como divisor de 2^{d}+1 para divisores d<n.
  • 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 3.

Passo 5

Construção explícita passo a passo (indutiva), evitando as exceções:
  • Começamos escolhendo um inteiro inicial m_{1} ímpar com m_{1}>1 e m_{1}\neq 3. Por simplicidade tomamos \;m_{1}=5\; (porque 2^{5}+1=33=3\cdot 11 tem o primo novo 11).
  • Pelo argumento do passo anterior (Zsigmondy para n=5) existe um primo p_{1} que divide 2^{m_{1}}+1 e que não divide 2^{d}+1 para nenhum divisor próprio d de m_{1}. Podemos escolher p_{1}=11.
  • Definimos m_{2}=m_{1}\cdot p_{1}. Observe que m_{2} é ímpar e maior que 1, e não é igual a 3.
  • Em geral, suponha que em algum passo k já temos um inteiro m_{k} que é produto de k primos distintos p_{1},\dots,p_{k}, todos ímpares, com m_{k}>1 e m_{k}\neq 3. (Isto é verdade para k=1 com m_{1}=5.)
  • Então, aplicando novamente o resultado (Zsigmondy) a 2^{m_{k}}+1 (já que m_{k} é ímpar e m_{k}\neq 3), existe um primo p_{k+1} que divide 2^{m_{k}}+1 e que não divide 2^{d}+1 para nenhum divisor próprio d de m_{k}. Esse p_{k+1} é um primo novo (não coincide com nenhum p_{1},\dots,p_{k}).
  • Definimos m_{k+1}=m_{k}\cdot p_{k+1}. Assim m_{k+1} tem exatamente k+1 primos distintos na sua fatoração.

Passo 6

Mostrando que cada m_{k} divide 2^{m_{k}}+1 (a propriedade que queremos):
  • Vamos provar por indução que, para cada k, todos os primos p_{1},\dots,p_{k} dividem 2^{m_{k}}+1. Logo o produto m_{k}=p_{1}\cdots p_{k} divide 2^{m_{k}}+1 (porque fatores são primos distintos, portanto coprimos entre si, e se cada um divide o número então o produto divide).
  • Base k=1: por construção p_{1} divide 2^{m_{1}}+1.
  • Passo indutivo: suponha que para k já sabemos que p_{1},\dots,p_{k} dividem 2^{m_{k}}+1. Ao escolher p_{k+1} nós tomamos um primo que divide 2^{m_{k}}+1. Agora m_{k+1}=m_{k}\cdot p_{k+1} e o quociente m_{k+1}/m_{k}=p_{k+1} é ímpar, portanto, pelo argumento do Passo 3, qualquer primo que divide 2^{m_{k}}+1 também divide 2^{m_{k+1}}+1. Assim p_{1},\dots,p_{k},p_{k+1} dividem 2^{m_{k+1}}+1. Isso conclui a indução.
  • Consequência: para cada k o número m_{k}=p_{1}\cdots p_{k} divide 2^{m_{k}}+1.

Passo 7

Concluindo para 2000 primos:
  • Repetindo o passo anterior 2000 vezes (começando em m_{1}=5 e aplicando o procedimento descrito), obtemos um inteiro m_{2000} que é produto de 2000 primos distintos p_{1},\dots,p_{2000} e que satisfaz \;m_{2000}\mid 2^{m_{2000}}+1.
  • Portanto tomando N=m_{2000} temos exatamente o que o enunciado pede: N é divisível por exatamente 2000 primos diferentes e N\mid 2^{N}+1.

Passo 8

Observações finais e verificação das hipóteses usadas:
  • É importante que em cada etapa o expoente seja ímpar e diferente de 3 para escapar da exceção \,2^{3}+1=9 onde não surge primo novo. Começamos em m_{1}=5, e a cada passo multiplicamos por primos ímpares, então todos os m_{k} permanecem ímpares e nunca igualam 3.
  • O uso do teorema de Zsigmondy (na forma prática que garante um divisor primo primitivo para 2^{n}+1 quando n é ímpar e n\neq 3) é 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 N\mid 2^{N}+1.
  • Assim, não só existe um N com a propriedade pedida, como existe um método explícito para construir um com qualquer número desejado de primos distintos (neste caso, 2000).

Resposta

Sim.

Exercícios relacionados