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