Dados
. Aplicando sucessivamente o algoritmo de Euclides temos:
:
como
temos que existe um primeiro inteiro
tal que
. Prove que
M.D.C.
.
:
como
Passo 1
O enunciado descreve a aplicação sucessiva do algoritmo de Euclides a dois inteiros positivos
e
, gerando restos
até que apareça o primeiro
tal que
. Precisamos mostrar que o último resto não nulo
é exatamente
. 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
,
De fato, como
qualquer divisor
comum a
e
também divide
logo divide
e
. Reciprocamente, se
divide
e
, então divide
Assim o conjunto de divisores comuns de
coincide com o de
, o que implica a igualdade dos seus maiores elementos. Aplicando isso repetidamente desde
até
obtemos
Passo 3
Como
, do resultado do passo anterior temos
E é sabido que, para todo inteiro
,
. Logo
e concluímos que