RE: [obm-l] Identidades de mdc

["David M. Cardoso" <david-obm@xxxxxxxxxxxx>]

Eu nao sei muita coisa sobre esse negocio,
Mas depois q eu li a mensagem do Fábio deu vontade
de tentar fazer esse seguindo o mesmo raciocinio.. ;)
[tomara q esteja certo]

> mdc(a,b) = mdc(a,a+b)

Seja d = (a,b)

a = di
b = dj

(a,a+b) = (di, di + dj) = d(i, i+j)

p = (i, i+j)

i = pk
i+j = pq
j = p(q-k)

como vimos, i e j sao primos entre si, logo p=1
i = k
j = q-k
i+j = q

(i, i+j) = (k, q)

Como vimos, k e q sao primos entre si, logo (i, i+j) = 1


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