Vidal, muito boa a sacada.
Eu tinha tentado escrever como o produto de dois polinômios de grau
2, sem sucesso.
Parabéns pela solução.
Um abraço.
.
On Apr 6, 2009, at 03:21 , *Vidal wrote:
Caros Fabrício e Nehab,
Achar um fator foi fácil, o problema foi "quebrar" o quociente nos
outros dois.
Fiz assim:
5^1985 - 1 = (5^397)^5 - 1
Seja x = 5^397.
Então queremos fatorar x^5 - 1 que, de imediato, resulta em (x - 1)
(x^4 + x^3 + x^2 + x + 1), ou seja, um dos fatores é 5^397 - 1.
Falta fatorar x^4 + x^3 + x^2 + x + 1 de uma forma conveniente.
Após um tempinho (pouca coisa, até no Fla x Flu no Maracanã estava
rabiscando...), tive a idéia de tentar escrever a expressão como
uma adequada diferença de dois quadrados. Caso conseguisse, o
problema estaria resolvido, pois um fator seria a soma e outro, a
diferença.
Arbitrei o primeiro quadrado como (x^2 + ax + 1)^2, que já geraria
o termo de quarto grau e o termo independente corretos.
E coloquei o segundo quadrado como 5x(x+b)^2, pois como x = 5^397,
5x = 5^398 seria um quadrado perfeito.
Igualando as expressões (e rezando para encontrar valores de a e b
compatíveis), veio:
(x^2 + ax + 1)^2 - 5x(x+b)^2 = x^4 + (2a -5)x^3 + (a^2 - 10b + 2)
x^2 + (2a - 5b^2)x + 1 = x^4 + x^3 + x^2 + x + 1
Assim:
2a -5 = 1 => a = 3
a^2 - 10b + 2 = 1 => b = 1
Agora era hora da onça beber água:
2a - 5b^2 = 1
Mas a = 3 e b = 1 satisfazem ! Eureka !
x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 - 5x(x+1)^2
Substituindo x por 5^397:
((5^397)^2 + 3*5^397 +1)^2 - 5*5^397*(5^397 + 1)^2 =
= ((5^397)^2 + 3*5^397 +1)^2 - 5^398*(5^397 + 1)^2 (diferença de
quadrados) =
= (((5^397)^2 + 3*5^397 +1) - 5^199*(5^397 + 1)) * (((5^397)^2 +
3*5^397 +1) + 5^199*(5^397 + 1)) (produto da diferença pela soma) =
= (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397
+ 5^199 + 1)
Os três fatores são claramente maiores que 5^100, conforme solicitado.
Então:
5^1985 -1 = (5^397 - 1) * (5^794 - 5^596 + 3*5^397 - 5^199 + 1) *
(5^794 + 5^596 + 3*5^397 + 5^199 + 1)
Como já são três da manhã e já perdi o sono mesmo, resolvi fazer
umas "continhas de cabeça", tal como o Ralph fez outro dia desses...
5^397-1 = 2 x 2 x 1.043.801.929 x 7.768.438.039 x C258
5^794 -5^596 + 3*5^397 - 5^199 + 1 = 71 x 399.091.951.801 x C542
5^794 + 5^596 + 3*5^397 + 5^199 + 1 = 11 x 146.891 x C549
Logo:
5^1985 -1 = 2 x 2 x 11 x 71 x 146.891 x 1.043.801.929 x
7.768.438.039 x 399.091.951.801 x C258 x C542 x C549
(onde Cn são números compostos de n algarismos).
A fatoração de C258, C542 e C549 fica como exercício ...
:)
Abraços,
Vidal.
P.S. Nehab: Apesar de não nos conhecermos pessoalmente, temos um
grande amigo em comum: o Manuel Martins Filho, professor de
Informática da Carioca ! Abraços !
:: [email protected]
***
2009/4/5 Carlos Nehab <[email protected]>
Oi, gente,
Fabricio postou este interessante problema e aparentemente ninguém
deu muita bola, talvez achando que é óbvio.
Não achei óbvio não. Quem resolveu?
Abraços,
Nehab
[email protected] escreveu:
Caros colegas,
mexendo em algumas listas antigas de exercícios, um me chamou
muito a atenção.
Pede pra fatorar 5^1985 - 1 num produto de três inteiros maiores
que 5^100.
Pra facilitar um possível avanço, 1985 pode ser escrito como 5 x
397 (ambos primos).
.
=====================================================================
====
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=====================================================================
====
======================================================================
=== Instruções para entrar na lista, sair da lista e usar a lista
em http://www.mat.puc-rio.br/~obmlistas/obm-l.html
======================================================================
===
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
