Para cada par de números naturais
e
dados abaixo, ache (
) e determine números inteiros
e
tais que
.
7325 e 8485
7325 e 8485
Passo 1
O enunciado dá os dois números naturais
e
e pede duas coisas: encontrar o máximo divisor comum
e determinar inteiros
e
tais que
As informações relevantes são apenas os dois números fornecidos; a tarefa é aplicar o algoritmo que calcula o MDC e, em seguida, expressá-lo como combinação linear dos dois números.
Passo 2
Vou usar o Algoritmo de Euclides para calcular o máximo divisor comum (MDC). Lembrete prático do algoritmo: dada uma divisão inteira
temos a propriedade importante
Ou seja, o MDC de
e
é o mesmo que o MDC de
e do resto
. Repetimos esse processo até obter resto zero; o último resto não nulo é o MDC.
Passo 3
Aplicando o Algoritmo de Euclides aos números
e
:
Primeira divisão:
Segunda divisão:
Terceira divisão:
Quarta divisão:
Como o resto ficou
na última divisão, o último resto não nulo é
. Portanto o MDC é
.
Passo 4
Resumo do que encontramos (para fixar): a cadeia de restos foi
logo
Passo 5
Agora precisamos escrever
como combinação linear de
e
, ou seja, achar inteiros
e
tais que
Para isso usamos o algoritmo extendido de Euclides: voltamos substituindo os restos pelas expressões obtidas nas divisões (back-substitution), reescrevendo cada resto como combinação linear dos dois números originais.
Passo 6
Fazemos a substituição passo a passo a partir da terceira divisão, onde achamos
:
Da terceira divisão temos
Da segunda divisão temos
Substituindo essa expressão de
em
:
Desenvolvendo:
Agora usamos a primeira divisão, que deu
Substituindo essa expressão de
na expressão anterior:
Desenvolvendo:
Passo 7
Interpretando o resultado na forma pedida, temos
Portanto uma solução inteira para
e
é
e
. Podemos checar mentalmente:
e
; a diferença é
, conferindo o cálculo.