Re: IMO-2000 --- problema 5

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Thu, 10 Aug 2000, Bruno Leite wrote:

> Oi pessoal
> 
> Agora estou enviando a minha solucao do quinto problema da IMO-2000.
> Corrijam-me se acharem alguma besteira...

Oi Bruno, infelizmente sua solução está errada, leia abaixo para ver porque:










solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...






















solução se aproxima...












> 
> Vou usar o sinal de igual para congruência.
> 
> Temos que 2^n+1 é multiplo de n e n é divisível por 2000 primos.
> Seja k o maior inteiro tal que 3^k divide n. Seja q o menor primo(fora o 3)
> que divide n (logo q>3). (ou ainda: q é o menor primo que divide n/(3^k)...
> ) E seja P=n/((3^k)*q). Veja que P é um produto de milhares de primos,
> contendo talvez uma potência de q em sua fatoração. Mas veja que qualquer
> primo de P é maior ou igual a q.
> 
> Entao n=q*P*3^k.
> Temos 2^n=-1(mod n) e portanto 2^n=-1(mod q)
> 2^(q*P*3^k)=-1(mod q) ->pelo pequeno teorema de Fermat ->  (2^(P*3^k))^q =
> -1 = 2^(P*3^k) (mod q)
> Logo
> 
>  2^(2*P*3^k) = 1 (mod q)
> 
> Seja r uma raiz primitiva mod q e seja u tal que r^u=2 (mod q), com 0<u<=q-1
> Então r^(2*P*u*3^k) = 1 (mod q)
> 
> Por isso q-1 divide 2*P*u*3^k

Até aqui parece estar tudo bem.
> 
> Mas q-1 não divide 3^k pois q-1 é par. E q-1 não divide P pois q-1 é menor
> que qualquer primo de P.

O número (q-1) não é primo. Assim o fato de um produto ser múltiplo
de (q-1) não significa que um dos fatores o seja.
> 
> Logo q-1 divide 2*u com 0<u<=q-1
> Por isso u=q-1 ou u=(q-1)/2
> 
> Como r^u=2(mod q), se u for q-1 teremos 1=2 mod q absurdo. Entao u=(q-1)/2
> Mas aí r^u=+-1(mod q) ->q=1(absurdo) ou q=3(absurdo por definicao de q)
> 
> Portanto não existe um tal n.
> ---------------------------------------
> 
> Bruno Leite
> 
> 
> 

Observe aliás que 171 = 3^2 * 19 satisfaz a condição
de 2^n+1 ser múltiplo de n (mas obviamente tem apenas 2 fatores promos).

[]s, N.