Use o algoritmo euclidiano para encontrar:
e
. Escreva o
, como combinação linear desses inteiros.
Passo 1
O enunciado nos pede para calcular o máximo divisor comum, isto é
, de cada par de inteiros
e
usando o algoritmo de Euclides, e em seguida expressar cada
como combinação linear dos dois inteiros correspondentes. O conteúdo envolvido é o algoritmo de Euclides e o algoritmo estendido para obter a combinação linear.
Passo 2
Aplicando o algoritmo de Euclides em
e
:
Como o resto chegou a zero, o último resto não nulo é
Passo 3
Agora estendemos para escrever
como combinação linear de
e
. Partimos da penúltima linha:
Mas
e
vêm das linhas anteriores:
Substituindo sucessivamente,
Logo,
Passo 4
Aplicando o algoritmo de Euclides em
e
:
Logo,
Passo 5
Para a combinação linear de
, partimos de
E temos
Substituindo em cadeia:
Logo,