Encontre inteiros
e
:
Passo 1
O enunciado pede: encontrar inteiros
e
tais que
Informações dadas:
- Os dois números são
e . - Quer-se escrever o máximo divisor comum desses números como combinação linear inteira dos dois: um inteiro multiplicando
mais um inteiro multiplicando .
Não se começa a resolver ainda — apenas listei o que é pedido e os dados.
Passo 2
Vamos primeiro calcular
usando o algoritmo de Euclides (divisões sucessivas). A ideia do algoritmo de Euclides é que
onde
é o resto da divisão de
por
. Aplicando:
Quando o resto vira
, o último resto não nulo é o
. Portanto
Explicando de forma simples: dividimos
por
, sobra
; dividimos
por
, sobra
; dividindo
por
sobra
, então o
é
.
Passo 3
Agora queremos escrever
como combinação linear
. Para isso usamos o algoritmo de Euclides estendido: voltamos nas igualdades obtidas e expressamos o último resto não nulo em função de
e
.
Das divisões temos as igualdades (repetindo):
Substituímos a expressão de
na expressão de
:
Distribuindo e reunindo termos em
e
:
Assim obtemos diretamente uma combinação linear.
Passo 4
Da igualdade anterior lemos os coeficientes:
Portanto uma solução inteira é
Sempre bom conferir:
, OK.
Passo 5
Também é útil saber todas as soluções inteiras. Se
é uma solução de
e
, então todas as soluções inteiras são dadas por
para todo
. Aqui
e
. Usando a solução particular
obtemos a família completa:
Verificação rápida com
:
,
e
, funciona.