Re: [obm-l] 2^33 - 2^19 - 2^17 - 1 de novo!

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

On Mon, Mar 17, 2003 at 06:25:18PM -0300, Rafael wrote:
> Oi Pessoal!
> 
> Andou por essa lista a seguinte pergunta: Como se
> mostra que 2 ^ 33 - 2 ^ 19 - 2 ^ 17 - 1 é divisível
> por 1983?
> 
> Mas eu já fui perguntado a mesma coisa de outra
> maneira: Determine um divisor de 2^33 - 2^19 - 2^17 -
> 1 entre 1000 e 5000.
> 
> Que é bem diferente porque você não sabe quem é o
> divisor, aí não pode simplesmente dividir o número e
> ver que a divisão é exata. Como fazer para chegar
> nesse divisor a partir dessa pergunta?

Não sei se você está pedindo algo mais eficiente ou mais esperto mas
com maple (ou algo parecido) é fácil. Primeiro fatoramos o número:

> ifactor(2 ^ 33 - 2 ^ 19 - 2 ^ 17 - 1);
                              3
                           (3)   (13)  (661)  (37021)

Bem, o fator que você quer não pode incluir 37021 (senão seria grande)
mas precisa incluir 661 (senão é pequeno). Não pode incluir 661*13
(senão é grande) logo é da forma 661*3^k. Testando 661*3 = 1983
serve mas 661*9 = 5949 já é grande demais.

[]s, N.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================