Olá , Esta questão realmente não é fácil , como de repente pode parecer . Ela foi proposta numa Olimpíada Internacional e não usada e, foi também proposta na RPM - 18 . A solução do Vidal teve um brilhantismo , pois explicou em detalhes os passos .
Abraços Carlos Victor 2009/4/6 Carlos Nehab <ne...@infolink.com.br> > Oi, Vidal (e Fabricio), > > Já que meu neto não está aqui em casa... :-) e como gostei tanto de suas > continhas de cabeça, fucei um site que tenho certeza que vocês vão > gostar.... Tem coisas surreais.... > http://www.leyland.vispa.com/numth/factorization/main.htm > > Abraços, > Nehab > ( > *Vidal escreveu: > > 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. > > :: vi...@mail.com > > > > 2009/4/6 fabrici...@usp.br <fabrici...@usp.br> > >> 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 ! >>> >>> :: vi...@mail.com >>> >>> *** >>> >>> 2009/4/5 Carlos Nehab <ne...@infolink.com.br> >>> 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 >>> >>> fabrici...@usp.br 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 >> ========================================================================= >> > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html=========================================================================
