Use o algoritmo de Euclides para obter números
e
satisfazendo
Passo 1
O enunciado pede que a gente encontre números inteiros
e
tais que
Informações dadas:
Objetivo imediato: usar o algoritmo de Euclides estendido para escrever
como combinação linear de
e
e assim obter
e
.
Passo 2
Vou aplicar o algoritmo de Euclides para achar o
. Lembra: o algoritmo faz divisões sucessivas para obter restos até o resto ser
; o último resto não-nulo é o
. Faço as divisões:
Passo 3
Do passo anterior o último resto não-nulo é
. Portanto
Isso é ótimo: como
divide
, existe solução inteira para
. Nosso próximo objetivo é expressar
como combinação linear
(a partir da decomposição acima) e depois multiplicar por
para obter os coeficientes procurados.
Passo 4
Agora faço a substituição regressiva (Euclides estendido) para escrever
como combinação de
e
.
Começo com a última divisão não-trivial:
Mas da divisão anterior temos
substituindo:
Agora uso
:
Em seguida uso
:
Por fim uso
:
Assim encontramos uma expressão para
:
Passo 5
Multiplico a expressão de
por
para obter
:
Distribuindo:
Portanto uma solução inteira é
e
.