[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Fatoração de 5 ^1985 - 1.
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
[obm-l] Re: [obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
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.htmlhttp://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.htmlhttp://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.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html =
Re: [obm-l] Re: [obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
Oi, Vidal (e Fabricio), J que meu neto no est aqui em casa... :-) e como gostei tanto de suas continhas de cabea, fucei um site que tenho certeza que vocs vo gostar Tem coisas surreais http://www.leyland.vispa.com/numth/factorization/main.htm Abraos, Nehab ( *Vidal escreveu: Caro Fabrcio, Eu tambm passei por esta etapa (produto de dois polinmios de grau 2) durante o "pequeno" tempo que pensei na soluo, depois de "provocado" pelo Nehab. Mas infelizmente os fatores no eram inteiros. Abraos, 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 polinmios de grau 2, sem sucesso. Parabns pela soluo. Um abrao. . On Apr 6, 2009, at 03:21 , *Vidal wrote: Caros Fabrcio e Nehab, Achar um fator foi fcil, o problema foi "quebrar" o quociente nos outros dois. Fiz assim: 5^1985 - 1 = (5^397)^5 - 1 Seja x = 5^397. Ento 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. Aps um tempinho (pouca coisa, at no Fla x Flu no Maracan estava rabiscando...), tive a idia de tentar escrever a expresso como uma adequada diferena de dois quadrados. Caso conseguisse, o problema estaria resolvido, pois um fator seria a soma e outro, a diferena. 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 expresses (e rezando para encontrar valores de a e b compatveis), 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 ona 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 (diferena 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 diferena pela soma) = = (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Os trs fatores so claramente maiores que 5^100, conforme solicitado. Ento: 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 so trs da manh e j perdi o sono mesmo, resolvi fazer umas "continhas de cabea", 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 so nmeros compostos de n algarismos). A fatorao de C258, C542 e C549 fica como exerccio ... :) Abraos, Vidal. P.S. Nehab: Apesar de no nos conhecermos pessoalmente, temos um grande amigo em comum: o Manuel Martins Filho, professor de Informtica da Carioca ! Abraos ! :: vi...@mail.com *** 2009/4/5 Carlos Nehab ne...@infolink.com.br Oi, gente, Fabricio postou este interessante problema e aparentemente ningum deu muita bola, talvez achando que bvio. No achei bvio no. Quem resolveu? Abraos, Nehab fabrici...@usp.br escreveu: Caros colegas, mexendo em algumas listas antigas de exerccios, um me chamou muito a ateno. Pede pra fatorar 5^1985 - 1 num produto de trs inteiros maiores que 5^100. Pra facilitar um possvel avano, 1985 pode ser escrito como 5 x 397 (ambos primos). . = Instrues para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instrues para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instrues para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
