[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
Re: [obm-l] Re: [obm-l] Fatoração de 5^ 1985 - 1.
Oi, Vidal, Muito legal a sacao bem sucedida de forar a diferena entre quadrados, e com muita criatividade ... Eu no tinha conseguido matar o problema. Quanto ao Manuel somos amigos h 30 anos e j percorremos muito cho juntos. Nos conhecemos no SERPRO, quando ramos funcionrios de uma rea maluca de Estatstica, Modelagem , etc (era onde eles colocavam os caras que, alm de programar, como todo mundo de l programava, sabiam tambm fazer umas continhas mgicas como a que voc fez no problema abaixo..). E nesta poca eu ainda dava aula no IME, de Lgica, Anlise Linear, Clculo ,1,2..., N..., etc). Pr voc ter uma idia meu cargo era de Matemgico Ahhh , que emoo quando penso nas pessoas bacanas com quem convivi naquela poca. Todas geniais... Gostosas saudades... Mas no sei se voc sabe, eu fui coordenador de Cursos de Computao da Carioca e Gerente de Tecnologia durante uns 2 anos, h uns 10 anos ... E l estava o Manuel que foi quem me seduziu a trabalhar l... Um grande abrao, Nehab PS: De onde voc conhece o Manuel? Da night? Dos botequins e rodadas de violo? Ou foi aluno dele? *Vidal escreveu: 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 = = Instruções para entrar na lista, sair da lista e usar a
[obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
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=
Re: [obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
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 =
[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 =
