---------- Cabeçalho original ----------- De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Fri, 30 Mar 2007 13:33:11 +0000 Assunto: [obm-l] raízes comuns e IME 56
> Sauda,c~oes, > > Oi Claudio, > > Seja mdc(m,n)=d. > > Como provar que mdc(x^n-1,x^m-1)=x^d-1 ? > Eh facil ver que x^d-1 divide x^m-1 e x^n-1. (m = kd ==> x^m-1 = x^(kd)-1 = (x^d)^k-1 = (x^d-1)*p(x)) Suponhamos agora que f(x) divide x^m-1 e x^n-1. Em particular, f(x) eh primo com x. d = (m,n) ==> existem inteiros positivos r e s tais que d = rm - sn. Alem disso, f(x) divide x^(rm)-1 e x^(sn)-1. Logo, f(x) divide (x^(rm)-1)-(x^(sn)-1) = x^(rm)-x^(sn) = x^(sn)*(x^(rm-sn)-1) = x^(sn)*(x^d-1). Mas f(x) eh primo com x^(sn). Logo, f(x) divide x^d-1. Ou seja, (x^m-1,x^n-1) = x^d-1. []s, Claudio. ========================================================================= 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 =========================================================================
