- (2 pontos) Expresse o MDC de 34 e 55 como uma combinação linear destes inteiros.
Passo 1
O enunciado pede que eu expresse o MDC de
e
como uma combinação linear desses inteiros. Ou seja, quero encontrar inteiros
e
tais que
Informações dadas: os dois inteiros
e
. Pergunta: achar
e
e escrever a identidade acima.
Passo 2
Vou usar o algoritmo de Euclides para calcular o
e depois o processo de retro-substituição (algoritmo estendido) para obter os coeficientes
e
. Antes de começar, rapidinho sobre a ideia (sem formalidade pesada): o algoritmo de Euclides aplica repetidas divisões com resto usando a propriedade de que
quando
. A cada passo reduzimos o problema até obter resto
; o último resto não nulo é o
.
Passo 3
Faço as divisões sucessivas entre
e
e depois entre os pares que aparecem, guardando quocientes e restos:
O último resto não-nulo é
, portanto
.
Passo 4
Agora vou escrever cada resto como combinação linear dos anteriores para, passo a passo, chegar a uma expressão de
em função de
e
. Primeiro, reorganizo as igualdades acima para isolar os restos (vou numerar as igualdades para facilitar):
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Começo a substituir da equação (7) para trás.
Passo 5
Substituo
usando (6) na (7):
Da (6):
.
Substituindo em (7):
Portanto:
Passo 6
Substituo
usando (5) onde
:
Portanto:
Passo 7
Substituo
usando (4) onde
:
Portanto:
Passo 8
Substituo
usando (3) onde
:
Portanto:
Passo 9
Substituo
usando (2) onde
:
Portanto:
Passo 10
Finalmente, substituo
usando (1) onde
:
Assim obtemos uma expressão de
como combinação linear de
e
.