Realmente muito interessante..gostei... e a questão da Bulgária que eu postei...vc viu???
> Acho que já havia respondido faz um tempo, mas, via > das dúvidas, aí vai de novo. A solução é um pouco > longa; prepare-se! > > Queremos mostrar que existe a tal que N = (a^29 - > 1)/(a-1) tem pelo menos 2007 fatores primos. > > Primeiro note que se a = x^2, temos > N = ((x^2)^29 - 1)/(x^2 - 1) > = [(x^29 + 1)/(x + 1)]*[(x^29 - 1)/(x - 1)]. > > Veja que (x^29 + 1)/(x + 1) e (x^29 - 1)/(x - 1) são > ambos inteiros (divida os polinômios!). Além disso, > sendo d = mdc(x^29 + 1, x^29 - 1), temos que x^29 + 1 > e x^29 - 1 são ambos múltiplos de d, o que implica em > (x^29 + 1) - (x^29 - 1) = 2 ser múltiplo de d. Logo d > = 1 ou d = 2. Se escolhermos x par, teremos d = 1. > > Assim, escolhendo x par, x^29 + 1 e x^29 - 1 têm mdc > igual a 1, ou seja, são primos entre si. Em outras > palavras, x^29 + 1 e x^29 - 1 não têm fatores primos > comuns. Deste modo, (x^29 + 1)/(x + 1) e (x^29 - 1)/(x > - 1) não podem ter fatores primos comuns (afinal, só > dividimos dois caras sem fatores comuns por outros > números; não é assim que vão aparecer fatores comuns, > certo?). > > Isso é legal pois faz aparecer fatores primos > diferentes: N = [(x^29 + 1)/(x + 1)][(x^29 - 1)/(x - > 1)] já tem pelo menos dois fatores primos distintos: > um de (x^29 + 1)/(x + 1) e outro de (x^29 - 1)/(x - 1) > (lembre-se, eles não têm fatores comuns, então não > podem aparecer primos repetidos). > > Tudo bem, ainda estamos longe de obter 2007 fatores > primos distintos, mas basta repetir a idéia! Lembrando > a fatoração de livro texto > x^4 - 1 = (x - 1)(x + 1)(x^2 + 1) > e, estendendo um pouco, > x^8 - 1 = (x - 1)(x + 1)(x^2 + 1)(x^4 + 1), > nota-se que > x^{2^2007} - 1 > = (x - 1)(x + 1)(x^2 + 1)...(x^{2^2006} + 1) > > Façamos, então, a = x^{2^2007}. Obtemos > N = [(x^{2^2007})^29 - 1]/[x^{2^2007} - 1] > > O numerador é igual a > (x^29-1)(x^29+1)(x^(2*29)+1)...(x^{2^2006*29}+1) > > De maneira completamente análoga à que fizemos acima, > provamos que quaisquer dois dos fatores acima são > primos entre si: basta notar que x^{2^k} + 1 e x^{2^k} > - 1 são primos entre si e "desfazer" a fatoração. Fica > mais fácil ver para x^{8*29} - 1, por exemplo: > x^{8*29} - 1 = (x^{4*29} - 1)(x^{4*29} + 1) > x^{4*29} + 1 e x^{4*29} - 1 são primos entre si; > portanto x^{4*29} + 1 é primo com todos os fatores de > x^{4*29} - 1. > x^{4*29} - 1 = (x^{2*29} - 1)(x^{2*29} + 1) > x^{2*29} + 1 e x^{2*29} - 1 são primos entre si e com > x^{4*29} + 1, etc. > > O denominador já calculamos lá em cima. > > Então (vou escrever na forma de fração mesmo): > (x^29-1)(x^29+1)(x^(2*29)+1)...(x^{2^2006*29}+1) > N = ------------------------------------------------, > (x - 1)(x + 1)(x^2 + 1)...(x^{2^2006} + 1) > que é igual ao produto dos 2007 inteiros da forma > (y^29-1)/(y-1) ou (y^29+1)/(y+1) > (x^29 - 1)/(x - 1), > (x^29 + 1)/(x + 1), > (x^{2*29} + 1)/(x^2 + 1), > ... > (x^{2^2006*29} + 1)/(x^{2^2006} + 1), > todos primos dois a dois. > > Cada um vai prover um primo diferente e, tomando x > par, obtemos (infinitos) N da forma (a^29 - 1)/(a - 1) > com pelo menos 2007 fatores primos distintos. > > Eu sei que a solução acima é um pouco longa, mas é por > isso que as provas da OBM têm 4 horas e meia, certo? > Além disso, a matéria usada é elementar, mesmo para > quem está no final do EF: fatoração, muito pouco de > polinômios, divisibilidade e mdc. > > []'s > Shine > > --- vitoriogauss wrote: > > > afinal..como ficou a solução da questão: > > > > > > (a^29 - 1)/a-1 , existem 2007 fatores 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 > ========================================================================= > Vitório Gauss