Hmmm.... Eu acho que o seguinte eh verdadeiro:
Lema: Considere a seguinte iteracao: dado o conjunto {x,y} com x>y>0,
troque-o por {x,x-y}. Eu afirmo que voce pode repetir esta iteracao
ateh ficar com o conjunto unitario {d} onde d=mdc{x_original,
y_original}.
Dem.: Pense como funciona o algoritmo para encontrar m.d.c., mas ao
inves de dividir x por y para achar x=qy+d, subtraia y de x (q vezes)
ateh ficar com d.
Agora, supondo n>m, qualquer divisor comum de a^n-1 e a^m-1 tem que
dividir a diferenca (a^n-a^m)=a^m (a^(n-m)-1), supondo n>m. Como a^m
eh primo com a^m-1, concluo que ele tem que ser divisor de a^(n-m)-1.
Alias, VAI E VOLTA: supondo n>m, b eh divisor comum de a^n-1 e a^m-1
SE, E SOMENTE SE, b eh divisor comum de a^m-1 e a^(n-m)-1.
Ou seja, os divisores comuns dessas expressoes nao mudam ao perfazer a
operacao de trocar {m,n} por {m,n-m}. Itere esta ideia e voce vai
chegar que b tem que ser divisor de a^d-1 onde d=mdc{m,n}. Entao nao
ha nada maior mesmo.
Abraco,
Ralph
2014-07-09 14:42 GMT-03:00 Arthur Max <[email protected]>:
> oi
>
> Em 08/07/14, Artur Costa Steiner<[email protected]> escreveu:
>> De nada!
>>
>> Podemos concluir de bate pronto que, dentre os divisores comuns de a^m - 1 e
>> a^n - 1 que sejam da forma a^r - 1, o maior 茅 a^d - 1. Mas n茫o sei pode
>> haver um divisor comum > a^ d - 1 que n茫o seja da forma a^r - 1. Vou
>> analisar mais.
>>
>> Artur Costa Steiner
>>
>>> Em 08/07/2014, 脿s 09:04, Pedro Chaves <[email protected]> escreveu:
>>>
>>> Muito obrigado, caro Artur, pela demonstra莽茫o do teorema abaixo:
>>> Teorema:
>>> Sendo a, n e m inteiros positivos, com a> 1, a^n - 1 divide a^m - 1 se, e
>>> somente se, n divide m.
>>>
>>> Bem... usando-se esse teorema, seria poss铆vel demonstrar que o
>>> mdc(a^n- 1, a^m - 1)= a^d - 1, sendo d = mdc(m, n)?
>>>
>>> Abra莽os do pedro Chaves!
>>> _______________________
>>>
>>>
>>>
>>> --
>>> Esta mensagem foi verificada pelo sistema de antiv铆rus e
>>> acredita-se estar livre de perigo.
>>>
>>>
>>> =========================================================================
>>> Instru莽玫es para entrar na lista, sair da lista e usar a lista em
>>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
>>> =========================================================================
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antiv铆rus e
>> acredita-se estar livre de perigo.
>>
>>
>> =========================================================================
>> Instru锟矫礶s para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
>> =========================================================================
>>
>
> --
> Esta mensagem foi verificada pelo sistema de antiv韗us e
> acredita-se estar livre de perigo.
>
>
> =========================================================================
> Instru珲es para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
