Caro Fabrício, Eu também passei por esta etapa (produto de dois polinômios de grau 2) durante o "pequeno" tempo que pensei na solução, depois de "provocado" pelo Nehab. Mas infelizmente os fatores não eram inteiros.
Abraços, Vidal. :: [email protected] 2009/4/6 [email protected] <[email protected]> > 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<http://www.mat.puc-rio.br/%7Eobmlistas/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<http://www.mat.puc-rio.br/%7Eobmlistas/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<http://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html> > ========================================================================= >
