Calcule
e
tais que M.D.C.
nos seguintes casos:
.
Passo 1
O enunciado pede para encontrar inteiros
e
tais que o máximo divisor comum de
e
se escreva como combinação linear
com
e
. Vamos usar o algoritmo de Euclides estendido, que consiste em aplicar o algoritmo de Euclides para calcular
e, em seguida, fazer o “back-substitution” para expressar esse valor como combinação linear de
e
.
Passo 2
Aplicamos o algoritmo de Euclides para encontrar
:
Como o resto zera em seguida, temos
Passo 3
Agora escrevemos
em termos dos restos anteriores. Da segunda linha:
Passo 4
Substituímos
pela expressão da primeira linha, onde
Logo,
Portanto, a combinação linear desejada é