[Fácil] Usando o algoritmo de Euclides estendido, escreva a identidade
para cada par
abaixo, encontrando inteiros
e
.
Passo 1
O enunciado pede: escrever a identidade
para o par
, isto é, encontrar inteiros
e
tais que a igualdade abaixo seja verdadeira:
As informações dadas são apenas os números
e
e a exigência de usar (implicitamente) o algoritmo estendido para obter
e
.
Passo 2
Primeiro vamos calcular
pelo algoritmo de Euclides (divisões sucessivas). Fazemos divisões sucessivas e anotamos quocientes e restos:
Quando o resto chega a
, o último resto não nulo é o
. Portanto
Passo 3
Agora precisamos escrever
como combinação linear de
e
. Para isso usamos as equações das divisões e fazemos substituições (este é o passo central do algoritmo de Euclides estendido). Reescrevemos os restos das divisões como expressões:
Da primeira divisão obtivemos
Da primeira divisão obtivemos
Da segunda divisão obtivemos
Passo 4
Substituímos a expressão de
(da primeira linha) na expressão de
(da segunda linha). Ou seja, em
troca-se
por
. Fazendo isso com calma:
Passo 5
Desenvolvendo a expressão passo a passo (distribuindo e recolhendo termos):
Passo 6
Agora está explícito
como combinação linear de
e
. Comparando com a forma
, vemos que
Vamos checar rapidamente:
, que é de fato o
.