[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Problemas em aberto - prob 10
Caro Demetrio,
Parece que os únicos contra-exemplos para isso são (A,B,C)=(2^m+1,2^m-1,2),
para m>=1. Além disso, acho que é possível provar algo bem mais forte (para
k grande): P tem pelo menos 2^k-k fatores primos distintos. Isso já é maior
que k+1 se k>=3. Vamos então provar isso primeiro e depois analisar os casos
k=1 e k=2.
Vamos usar polinômios ciclotômicos, que são polinômios phi_n(x),
indexados pelos inteiros positivos n que aparecem na fatoração de x^n-1:
para cada inteiro positivo n, x^n-1=produto(d divide n)(phi_d(x)). Isso
define os phi_n(x) por recorrência; temos
phi_n(x)=produto(1<=k<=n,mdc(k,n)=1)(x-e^(2.k.pi.i/n)), donde o grau de
phi_n(x) é phi(n) (aqui phi é a função de Euler). Segue da primeira
definição, via fatoração, por indução, que, para todo n, phi_n(x) tem
coeficientes inteiros e coeficiente líder 1. É possível provar que, para
todo n, phi_n(x) é um polinômio irredutível, mas não vamos usar isso aqui.
Temos A^c-B^c=B^c.((A/B)^c-1)=B^c.produto(d divide c)(phi_d(A/B))=
=produto(d divide c)(B^phi(d).phi_d(A/B)). Como phi_d(x) é um polinômio
mônico com coeficientes inteiros de grau phi(d), m_d:=B^phi(d).phi_d(A/B) é
inteiro, e produto(d divide c)(m_d)=A^c-B^c (e logo m_d é divisor de A^c-B^c,
para todo d divisor de c). Note que c tem 2^k divisores, e assim conseguimos
escrever A^c-B^c como produto dos 2^k números m_d. Vamos agora examinar
possíveis fatores primos comuns dos m_d. Vejamos primeiramente que se q é um
primo que não divide mmc(d,r) então q não pode dividir simultaneamente m_d e
m_r (desde que d seja distinto de r). De fato, f(x)=B^d.phi_d(x/B) e
g(x)=B^r.phi_r(x/B) são fatores de x^mmc(d,r)-B^mmc(d,r), e se m_d=f(A) e
m_r=g(A) são múltiplos de q, A é raiz pelo menos dupla de
x^mmc(d,r)-B^mmc(d,r) módulo q (isto é, sobre o corpo Z/qZ), donde é raiz de
sua derivada mmc(d,r).x^(mmc(d,r)-1). Como q não divide mmc(d,r), deve
dividir A^(mmc(d,r)-1), donde divide A, mas A é primo com B, e logo q não
divide d e portanto não pode pode dividir A^d-B^d, absurdo.
Isso mostra que se q é um primo que divide dois termos distintos m_d e
m_r então q tem que ser um dos divisores n_i de c, e nesse caso n_i deve ser
um divisor de d ou de r, donde n_i divide no máximo um termo m_d sem que d
seja múltiplo de n_i. Observemos agora que, se q é primo e q não divide r,
então phi_(qr)(x)=phi_r(x^q)/phi_r(x), o que pode ser verificado a partir
das raízes dos polinômios envolvidos. Se olharmos tudo módulo q (i.e., em
Z/qZ[x]), temos phi_r(x^q)=(phi_r(x))^q (pois (x+y)^q=x^q+y^q mod q para
quaisquer x,y e n^q=n mod q para n inteiro), donde
phi_(qr)(x)=(phi_r(x))^(q-1) módulo q, donde phi_(qr)(x)=0 (mod q) se e só
se phi_r(x)=0 (mod q) para todo x em Z/qZ. Em particular, fazendo q=n_i,
x=A/B, e usando o fato de c (e logo todos os n_i) ser primo com B, temos
que, se n_i não divide d, m_d é divisível por n_i se e só se n_i divide
m_(n_i.d). Isso mostra que cada n_i divide no máximo dois termos m_r (para
r=d e para r=n_i.d, se existir esse d divisor de c/n_i tal que n_i divide
m_d). Assim, como A^c-B^c é produto dos 2^k números m_r, todos maiores que
1, e no máximo k pares desses números têm fator comum, A^c-B^c tem pelo
menos 2^k-k fatores primos distintos. (cqd).
Se k=1, c=p é primo e, pela prova acima, se A^c-B^c só tem um fator
primo, A^c-B^c=A^p-B^p deve ser uma potência de p, e A-B também. Assim,
A=B+p^k, e A^p-B^p=(B+p^k)^p-B^p=B^(p-1).p^(k+1) (mod p^(k+2)) se p>=3 ou se
p=2 e k>1. Assim, nesses casos, a maior potência de p que divide A^p-B^p é
p^(k+1), donde a maior potência de p que divide (A^p-B^p)/(A-B) é p, e logo
A^(p-1)+A^(p-2).b+...+B^(p-1)=(A^p-B^p)/(A-B)=p (pois é uma potência de p),
e logo 2^(p-1)<=A^(p-1)<p, absurdo. Assim, p=2 e k=1, donde
A^p-B^p=(B+2)^2-B^2=4(B+1), que é uma potência de 2, donde B=2^m-1 e
A=2^m+1, como havíamos dito no começo desta mensagem.
Finalmente, se k=2, c=p.q, com p<q, A^c-B^c=m_1.m_p.m_q.m_(pq), e, pela
prova acima, se tivessemos exatamente 2=2^2-2 fatores primos distintos de
A^c-B^c, esses fatores deveriam ser p e q. Assim, A^(pq)-B^(pq) é uma
potência de p vezes uma potência de q, e logo
(A^(pq)-B^(pq))/(A^p-B^p)=m_q.m_(pq) também é uma potência de p vezes uma
potência de q. Se A^p-B^p é múltiplo de p, digamos A^p=B^p+k.p^r, onde p não
divide k, A^(pq)-B^(pq)=(B^p+k.p^r)^q-B^(pq)=q.B^p.(k.p^r) (mod p^(2r)),
donde é múltiplo de p^r e não de p^(r+1), e logo (A^(pq)-B^(pq))/(A^p-B^p)
não é múltiplo de p. Por outro lado, se A^(pq)-B^(pq) é múltiplo de p, e
A^p-B^p não é múltiplo de p, A^p/B^p não é 1 módulo p, mas (A^p/B^p)^q é 1
módulo q, donde a ordem módulo p de (A^p/B^p) é q, pois q é primo, mas q não
divide phi(p)=p-1 (pois q é maior que p), absurdo. Assim,
(A^(pq)-B^(pq))/(A^p-B^p) não é múltiplo de p e logo é uma potência de q.
Assim, A^(pq)-B^(pq) é múltiplo de q, e, como A^(pq)=(A^p)^q é congruente a
A6p módulo q, assim como B^(pq) é congruente a B^p módulo q, A^p-B^p também
é múltiplo de q, digamos A^p=B^p+s.q^r, donde
A^(pq)-B^(pq)=(B^p+s.q^r)^q-B^(pq)=s.B^p.q^(r+1) (mod q^(r+2)), pois q é
primo ímpar, donde a maior potência de q que divide A^(pq)-B^(pq) é q^(r+1),
e logo a maior potência de q que divide (A^(pq)-B^(pq))/(A^p-B^p) é q, donde
(A^(pq)-B^(pq))/(A^p-B^p)=q (pois é uma potência de q). Entretanto,
(A^(pq)-B^(pq))/(A^p-B^p)=A^(p(q-1))+A^(p(q-2))B^p+...+B^(p(q-1))>A^(p(q-1))>
>2^(q-1)>q, pois q>=3, absurdo.
Abraços,
Gugu
>
>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
>=========================================================================
>
=========================================================================
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
=========================================================================