Utilize o Algoritmo de Euclides para determinar os inteiros
e
tais que
.
(a)
e
;
(a)
Passo 1
O enunciado dá os inteiros
e
e pede para encontrar inteiros
e
tais que
Ou seja, encontrar
que expressem o máximo divisor comum de
e
como combinação inteira dessas duas quantidades. Vou primeiro calcular
e depois encontrar
e
por retro-substituição (Algoritmo de Euclides estendido).
Passo 2
Aplicando o Algoritmo de Euclides (divisões sucessivas) para
e
. Escrevo as divisões com quocientes e restos:
Explicando: em cada linha dividi o maior número pelo menor, e o resto vai diminuindo até chegar a zero. O último resto não nulo é o
.
Passo 3
Como o último resto não nulo é
(na segunda linha o resto foi
e depois o próximo resto é zero), concluímos que
Passo 4
Agora a parte pedagógica sobre como obter
e
: tomar as equações das divisões (as que fornecem os restos) e rearranjá-las para escrever cada resto como combinação linear dos números
e
; em seguida fazer substituições para expressar o último resto não nulo (
) como combinação linear de
e
. Vou fazer isso passo a passo.
Passo 5
Da primeira divisão temos o resto
; isolo-o:
Da segunda divisão temos o resto
; isolo-o:
Agora substituo a expressão de
(obtida acima) na expressão de
:
Desenvolvendo e recolhendo termos:
Passo 6
Interpretando a última linha:
foi escrito como combinação linear de
e
. Isso significa que
Para conferir rapidamente:
, OK. Assim encontramos os inteiros procurados.