Para cada par de números naturais
e
dados abaixo, ache (
) e determine números inteiros
e
tais que
.
637 e 3887
637 e 3887
Passo 1
O enunciado pede duas coisas para os números naturais dados
e
: (1) achar
, isto é, o máximo divisor comum de
e
; (2) determinar inteiros
e
tais que
.
Informações dadas: e
. Não vou resolver nada ainda — só organizei o que é pedido e o que foi dado.
Informações dadas:
Passo 2
Explicação do método que vamos usar (Algoritmo de Euclides + algoritmo extendido), de forma didática.
O Algoritmo de Euclides permite calcular fazendo divisões sucessivas com resto: a cada passo escrevemos
O Algoritmo de Euclides permite calcular
onde
é o dividendo,
o divisor,
o quociente inteiro e
o resto com
. Repetimos até obter resto zero; o último resto não nulo é o
.
O algoritmo estendido faz a mesma sequência de divisões, mas guarda como cada resto é combinação linear de e
; no final obtemos inteiros
tais que
. Vou primeiro executar as divisões e depois fazer a substituição para achar
e
.
O algoritmo estendido faz a mesma sequência de divisões, mas guarda como cada resto é combinação linear de
Passo 3
Executando o Algoritmo de Euclides para
e
. Colocamos sempre o maior primeiro; aqui
, então dividimos
por
.
Divisão 1:
porque
e
.
Divisão 2:
porque
e
.
Divisão 3:
porque
e
.
Divisão 4:
Como o resto tornou-se
, o último resto não nulo é
. Portanto
.
Passo 4
Agora o algoritmo estendido: vamos escrever o último resto não nulo
como combinação linear de
e
usando as igualdades das divisões e fazendo substituições (back-substitution). Vou explicar com calma cada substituição para você conseguir replicar na prova.
Das divisões anteriores temos, reescrevendo os restos isolados:
A ideia é eliminar os restos intermediários (
e
) substituindo as expressões (1) e (2) dentro de (3) até obter
em termos de
e
.
Passo 5
Primeira substituição: usar (2) dentro de (3) para eliminar
. A igualdade (3) é
Substituímos
por
(pela (2)):
Ou seja,
Passo 6
Segunda substituição: agora eliminar
usando (1). Da (1) temos
. Substituindo em
:
Portanto chegamos à escrita de
como combinação linear de
e
:
Passo 7
Interpretação final e verificação (importante na prova): isto significa que podemos escolher
e
tais que
tomando
e
. Vamos checar numericamente (fazendo as contas sem calculadora passo a passo, como você faria na prova):
Calcule
e some mais
para obter
. Então
.
Agora . Somando:
Agora
confirmando que a combinação está correta.