[SPAM] Re: [obm-l] Questão da Terceira fase N2

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

SPAM: -------------------- Start SpamAssassin results ----------------------
SPAM: This mail is probably spam.  The original message has been altered
SPAM: so you can recognise or block similar unwanted mail in future.
SPAM: See http://spamassassin.org/tag/ for more details.
SPAM: 
SPAM: Content analysis details:   (7.00 hits, 5 required)
SPAM: IN_REP_TO          (-0.8 points) Found a In-Reply-To header
SPAM: X_MAILING_LIST     (-0.3 points) Found a X-Mailing-List header
SPAM: SPAM_PHRASE_00_01  (0.8 points)  BODY: Spam phrases score is 00 to 01 (low)
SPAM: FORGED_YAHOO_RCVD  (1.4 points)  'From' yahoo.com does not match 'Received' headers
SPAM: RCVD_IN_ORBS       (2.2 points)  RBL: Received via a relay in orbs.dorkslayers.com
SPAM:                    [RBL check: found 199.36.190.206.orbs.dorkslayers.com., type: 68.178.232.99]
SPAM: RCVD_IN_OSIRUSOFT_COM (0.4 points)  RBL: Received via a relay in relays.osirusoft.com
SPAM:                    [RBL check: found 199.36.190.206.relays.osirusoft.com.]
SPAM: RCVD_IN_RELAYS_ORDB_ORG (0.6 points)  RBL: Received via a relay in relays.ordb.org
SPAM:                    [RBL check: found 20.158.207.200.relays.ordb.org.]
SPAM: X_OSIRU_OPEN_RELAY (2.7 points)  RBL: DNSBL: sender is Confirmed Open Relay
SPAM: 
SPAM: -------------------- End of SpamAssassin results ---------------------

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 <vitoriogauss@xxxxxxxxxx> 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
=========================================================================