Encontre o máximo divisor comum dos seguintes inteiros e sua expressão como combinação linear desses inteiros pelo Algoritmo de Euclides:
(a) 232 e 136;
(a) 232 e 136;
Passo 1
O enunciado pede duas coisas para os inteiros dados: (i) o máximo divisor comum (MDC) de
e
; (ii) expressar esse MDC como combinação linear desses inteiros, isto é, encontrar inteiros
e
tais que
As informações dadas são apenas os dois números
e
.
Passo 2
Vou usar o Algoritmo de Euclides. A ideia básica (fórmula de divisão) é: para inteiros
e
existem inteiros
e
com
tais que
O ponto importante é que
. Repetindo divisões sucessivas até o resto ser zero, o último resto não nulo é o MDC.
Passo 3
Começo aplicando a divisão com
e
:
Aqui o quociente é
e o resto é
.
Passo 4
Agora divido
por
:
Quociente
, resto
.
Passo 5
Divido
por
:
Quociente
, resto
.
Passo 6
Divido
por
:
Quociente
, resto
.
Passo 7
Divido
por
:
Aqui o resto é
, então o último resto não nulo é
. Portanto
Passo 8
Agora vamos obter a combinação linear (algoritmo extensivo de Euclides): voltamos nas igualdades acima e expressamos
como combinação linear de
e
. Reescrevo as igualdades relevantes (peguei estes dados das divisões feitas acima):
Passo 9
Começo isolando o resto
da última linha:
Passo 10
Substituo
usando a terceira linha onde
. Assim
Passo 11
Substituo
usando a segunda linha onde
. Então
Passo 12
Substituo
usando a primeira linha onde
. Assim
Passo 13
Verificação rápida (confirmação): calculemos
:
confirmando que a combinação está correta.