Dados a, b in N-0. Aplicando sucessivamente o algoritmo de Euclides temos:
a=q0 b+r1, 0 <= r1<b
b=q1 r1+r2, 0 <= r2<r1
r1=q2 r2+r3, 0 <= r3<r2
:
rk=qk+1 rk+1+rk+2, 0 <= rk+2<rk+1
como r1>r2>r3>ldots>rk>rk+1 >= 0 temos que existe um primeiro inteiro s tal que rs+1=0. Prove que rs= M.D.C. a, b.

Passo 1

O enunciado descreve a aplicação sucessiva do algoritmo de Euclides a dois inteiros positivos a e b, gerando restos
a = q0b + r1, b = q1r1 + r2, dots, rk = qk+1rk+1 + rk+2,
até que apareça o primeiro s tal que rs+1=0. Precisamos mostrar que o último resto não nulo rs é exatamente gcd(a,b). Para isso vamos usar a ideia de que os divisores comuns de dois números não mudam quando se passa para o par “menor, resto”.

Passo 2

Mostramos que, para cada i>=1,
gcd(ri-1,ri) ;=;gcd(ri,ri+1)
De fato, como
ri-1 = qi,ri + ri+1,
qualquer divisor d comum a ri-1 e ri também divide
ri+1 = ri-1 - qi,ri,
logo divide ri e ri+1. Reciprocamente, se d divide ri e ri+1, então divide
ri-1 = qi,ri + ri+1
Assim o conjunto de divisores comuns de (ri-1,ri) coincide com o de (ri,ri+1), o que implica a igualdade dos seus maiores elementos. Aplicando isso repetidamente desde (a,b) até (rs-1,rs) obtemos
gcd(a,b) = gcd(b,r1) = cdots = gcd(rs-1,rs)

Passo 3

Como rs+1=0, do resultado do passo anterior temos
gcd(rs-1,rs) ;=;gcd(rs,rs+1) ;=;gcd(rs,0)
E é sabido que, para todo inteiro n>=1, gcd(n,0)=n. Logo
gcd(rs,0) = rs,
e concluímos que
gcd(a,b) = rs

Resposta

rs = MDCa,b

Exercícios relacionados