[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Problemas em aberto - prob 10
Acho q vc tem raz�o... n�o me ocorre como consertar,
exceto colocando uma restri��o adicional. Acho que s�
vale para A-B e c, primos entre si.
[]�s
--- Carlos Gustavo Tamm de Araujo Moreira
<gugu@impa.br> escreveu:
> Caro Demetrio,
> No fim da sua explicacao, A-B nao pode ser uma
> potencia de y ? Nesse
> caso, todos os fatores primos de A-B sao fatores
> primos de y.A^(y-1), e eu
> nao entendi como voce conclui.
> Abracos,
> Gugu
>
> >
> > --- Claudio Buffara <claudio.buffara@terra.com.br>
> >escreveu:
> >
> >> *****
> >>
> >> 10) Seja P = A^c - B^c,
> >> onde:
> >> A, B e c s�o inteiros e primos entre si,
> >> A - B > 1,
> >> c = n1*n2*...*ni*...nk ,
> >> (os ni s�o fatores primos distintos, ou seja, c
> tem
> >> k fatores
> >> primos distintos).
> >>
> >> Mostre que P � um n�mero composto com, no m�nimo,
> >> k+1
> >> fatores primos distintos.
> >>
> >> *****
> >
> >Deixe eu colocar uma restri��o adicional c = impar.
> >
> >
> >Em primeiro lugar � f�cil ver que todos os n�meros
> >da forma A^ni - B^ni dividem P.
> >
> >Portanto, um caminho seria mostrar que, dados
> >quaisquer n�meros da forma S1 = A^x - B^x e
> >S2 = A^y - B^y, x e y primos entre si, S1 e S2 n�o
> >podem ser m�ltiplos, isto �, possuem algum fator
> >primo distinto entre si.
> >
> >
> >
> >****1**
> >suponha A, B e x,y primos entre si. x e y primos
> >diferentes de 2 e x > y.
> >
> >Hip�tese: se A^x - B^x tem fatores primos em
> >comum com A^y - B^y, estes fatores est�o em A - B.
> >
> >
> >Suponha que S1 = A^x - B^x cont�m um fator em
> >comum com S2 = A^y - B^y.
> >Seja
> >F1 = A^(x-y) * S2 = A^(x-y) * (A^y - B^y) =
> >A^x - [A^(x-y)*(B^y)].
> >
> >Naturalmente F1 cont�m o mesmo fator em comum
> >com S1 e S2, e portanto F1 - S1 o conter� tamb�m.
> >
> >F1 - S1 = B^x - [A^(x-y)*(B^y)] =
> >B^y * [B^(x-y) - A^(x-y)].
> >
> >Dado que A e B s�o primos entre si, o fator comum
> >n�o pode estar em B^y, e portanto est� em
> >B^(x-y) - A^(x-y).
> >
> >Agora pode-se repetir o racioc�nio para
> >B^(x-y) - A^(x-y) e A^y - B^y,
> >verificando qual dos dois expoentes � maior.
> >Suponhamos que x-y > y. Neste caso podemos provar
> >que o fator comum tamb�m est� em B^(x-2y) -
> A^(x-2y).
> >Observe que, caso y > x-y provar�amos para o
> >expoente 2y - x.
> >
> >Repetindo o racioc�nio interativamente vamos chegar
>
> >at� o expoente 1. Note que, como x e y s�o primos,
>
> >a sequencia de expoentes decrescentes n�o
> coincidir�
> >com y.
> >
> >Por exemplo x = 19, y = 3.
> >19 -> 16 -> 13 -> 10 -> 7 -> 4 ->1
> >
> >Por exemplo x = 17, y = 3.
> >17 -> 14 -> 11 -> 8 -> 5 -> 2 ->1
> >
> >Por exemplo x = 19 y = 11.
> >19 -> 8 -> 3 (11 - 8) -> 5 (8 - 3) -> 2 (5 - 3) ->
> 1
> >(3 - 2)
> >
> >
> >****2**
> >S2 = A^y - B^y tamb�m possui ao menos um fator
> primo
> >distinto da decomposi��o em fatores primos de A -
> B.
> >
> >Note-se que
> >S2 = (A - B) * F3, onde
> >F3 = A^y-1 + (A^(y-2))*B + ... + B^y-1
> >
> >Portanto, se a hip�tese estiver correta e S2
> >contiver ao menos um fator primo distinto de A - B,
>
> >este fator estar� em F3
> >
> >Note-se que F3 tem exatamente y termos.
> >Se a Hip�tese estiver incorreta, isto �, se A - B
> >contiver todos os fatores primos de F3, ent�o
> qualquer
> >
> >combina��o linear do tipo k1*(A - B) + k2*F3
> tamb�m
> >conter� todos estes fatores.
> >
> >Esta id�ia pode ser usada para reduzir-se os termos
>
> >de F3 at� um �nico termo que obrigatoriamente teria
>
> >de conter todos os fatores primos.
> >
> >Por exemplo vamos considerar y = 3.
> >Neste caso F3 = A^2 +A*B +B^2
> >
> >F3 + A(A - B) = A^2 + A*B - A*B + B^2 = 2*A^2 + B^2
> >2*A^2 + B^2 + (A + B)*(A - B) =
> >2*A^2 + B^2 + A^2 - B^2 = 3*A^2
> >
> >y = 5, F3=A^4 +A^3*B +A^2*B^2 +A*B^3 +B^4
> >F3 + A^3*(A - B) + A*B^2*(A - B) =
> >2*A^4 +2*A^2*B^2 +B^4 = X1
> >
> >X1 + 2*A^2*(A + B)*(A - B) = X1 + 2*A^4 -
> 2*A^2*B^2=
> > 4*A^4 + B^4
> >
> >4*A^4 + B^4 + A^4 - B^4 = 5*A^4
> >
> >Na verdade, caso (A - B) tenha todos os fatores
> primos
> >de F3, � poss�vel transformar F3 em outras
> express�es
> >que devem conter os mesmos fatores primos, atrav�s
> de
> >"opera��es elementares", at� uma express�o na forma
>
> >y*A^y-1 (ou y*B^y-1). Mas vamos recordar que A,B e
> y
> >s�o primos entre si, portanto n�o � poss�vel
> >que y*A^y-1 contenha os mesmos fatores primos de A
> -
> >B.
> >
> >
> >Em resumo, temos que
> >**1** - Se S1 e S2 possuem fatores primos em comum,
>
> >estes fatores est�o em A - B.
> >
> >**2** - S1 e S2 possuem ao menos um fator primo n�o
>
> >contido em A - B
> >
> >Logo S1 e S2 possuem ao menos um fator distinto
> entre
> >si.
> >
> >A extens�o para c par � direta fazendo A^2 - B^2
> >= D - C
> >
> >[]�s
> >
> >
> >
> >
> >
>
>_______________________________________________________
>
> >Yahoo! Acesso Gr�tis - Instale o discador do Yahoo!
> agora. http://br.acesso.yahoo.com/ - Internet r�pida
> e gr�tis
>
>=========================================================================
> >Instru��es para entrar na lista, sair da lista e
> usar a lista em
> >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
>=========================================================================
> >
>
>
=========================================================================
> Instru��es para entrar na lista, sair da lista e
> usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
=========================================================================
>
=== message truncated ===
_______________________________________________________
Yahoo! Acesso Gr�tis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet r�pida e gr�tis
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================