Desculpa pela mensagem errada pessoal, foi um amigo da faculdade quando deixei meu e-mail aberto no lab.
[]'s Em 09/07/14, Ralph Teixeira<[email protected]> escreveu: > 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 > ========================================================================= > -- 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 =========================================================================
