[Fácil] Usando o algoritmo de Euclides estendido, escreva a identidade
para cada par
abaixo, encontrando inteiros
e
.
Passo 1
O enunciado pede que a gente use o algoritmo de Euclides estendido para escrever a identidade
para o par dado
, ou seja: encontrar inteiros
e
tais que a combinação linear
seja igual a
. As informações que temos são apenas os valores
e
.
Passo 2
Primeiro passo prático: aplicar o algoritmo de Euclides (divisões sucessivas) para encontrar o
. Em cada linha eu escrevo a divisão com quociente e resto:
Esses restos foram obtidos aplicando a divisão inteira em cada linha. O algoritmo termina quando o resto fica zero.
Passo 3
O último resto não nulo é o
. Aqui o último resto não nulo é
(vem da linha
), portanto
Agora precisamos escrever esse
como combinação linear de
e
.
Passo 4
Explicação do método de retro-substituição (como funciona a parte “estendida”): cada resto nas linhas acima já foi escrito em função dos dois números anteriores. Podemos partir da igualdade que deu resto
e substituir recursivamente cada resto pelas expressões que aparecem nas linhas anteriores, até expressarmos
em termos de
e
. Vou fazer isso passo a passo, sem pular contas.
Começamos com a linha que produziu
:
Passo 5
Agora substituímos
pela expressão da linha anterior: da linha
temos
. Substituindo:
Passo 6
Substituímos
usando a linha
, ou seja
:
Passo 7
Substituímos
usando
, ou seja
:
Passo 8
Substituímos
usando
, logo
:
Passo 9
Substituímos
usando
, logo
:
Passo 10
Substituímos
usando
, logo
:
Passo 11
Finalmente substituímos
usando
, ou seja
:
Somando os coeficientes de
obtemos
. Assim:
Passo 12
Interpretação final: escrevemos
como combinação linear dos dois números. Aqui
e os coeficientes inteiros são
e
. Sempre é bom checar substituindo:
(confere).