---------- 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
=========================================================================

Responder a