[Fácil] Usando o algoritmo de Euclides estendido, escreva a identidade
\operatorname{mdc}(a, b)=a u+b v
para cada par (a, b) abaixo, encontrando inteiros u e v.
(a, b)=(1402,1969)

Passo 1

O enunciado pede que a gente use o algoritmo de Euclides estendido para escrever a identidade
\operatorname{mdc}(a,b)=a\,u+b\,v
para o par dado (a,b)=(1402,1969), ou seja: encontrar inteiros u e v tais que a combinação linear 1402\cdot u + 1969\cdot v seja igual a \operatorname{mdc}(1402,1969). As informações que temos são apenas os valores a=1402 e b=1969.

Passo 2

Primeiro passo prático: aplicar o algoritmo de Euclides (divisões sucessivas) para encontrar o \operatorname{mdc}. Em cada linha eu escrevo a divisão com quociente e resto:
1969 = 1\cdot 1402 + 567
1402 = 2\cdot 567 + 268
567 = 2\cdot 268 + 31
268 = 8\cdot 31 + 20
31 = 1\cdot 20 + 11
20 = 1\cdot 11 + 9
11 = 1\cdot 9 + 2
9 = 4\cdot 2 + 1
2 = 2\cdot 1 + 0
Esses restos foram obtidos aplicando a divisão inteira em cada linha. O algoritmo termina quando o resto fica zero.

Passo 3

O último resto não nulo é o \operatorname{mdc}. Aqui o último resto não nulo é 1 (vem da linha \;9 = 4\cdot 2 + 1\;), portanto
\operatorname{mdc}(1402,1969)=1.
Agora precisamos escrever esse 1 como combinação linear de 1402 e 1969.

Passo 4

Explicação do método de retro-substituição (como funciona a parte “estendida”): cada resto nas linhas acima já foi escrito em função dos dois números anteriores. Podemos partir da igualdade que deu resto 1 e substituir recursivamente cada resto pelas expressões que aparecem nas linhas anteriores, até expressarmos 1 em termos de 1402 e 1969. Vou fazer isso passo a passo, sem pular contas.
Começamos com a linha que produziu 1:
1 = 9 - 4\cdot 2.

Passo 5

Agora substituímos 2 pela expressão da linha anterior: da linha \;11 = 1\cdot 9 + 2\; temos 2 = 11 - 1\cdot 9. Substituindo:
1 = 9 - 4\cdot(11 - 1\cdot 9) = 9 - 4\cdot 11 + 4\cdot 9 = 5\cdot 9 - 4\cdot 11.

Passo 6

Substituímos 9 usando a linha \;20 = 1\cdot 11 + 9\;, ou seja 9 = 20 - 1\cdot 11:
1 = 5\cdot(20 - 1\cdot 11) - 4\cdot 11 = 5\cdot 20 -5\cdot 11 -4\cdot 11 = 5\cdot 20 -9\cdot 11.

Passo 7

Substituímos 11 usando \;31 = 1\cdot 20 + 11\;, ou seja 11 = 31 - 1\cdot 20:
1 = 5\cdot 20 -9\cdot(31 - 1\cdot 20) = 5\cdot 20 -9\cdot 31 +9\cdot 20 = 14\cdot 20 -9\cdot 31.

Passo 8

Substituímos 20 usando \;268 = 8\cdot 31 + 20\;, logo 20 = 268 - 8\cdot 31:
1 = 14\cdot(268 - 8\cdot 31) -9\cdot 31 = 14\cdot 268 -112\cdot 31 -9\cdot 31 = 14\cdot 268 -121\cdot 31.

Passo 9

Substituímos 31 usando \;567 = 2\cdot 268 + 31\;, logo 31 = 567 - 2\cdot 268:
1 = 14\cdot 268 -121\cdot(567 - 2\cdot 268) = 14\cdot 268 -121\cdot 567 +242\cdot 268 = 256\cdot 268 -121\cdot 567.

Passo 10

Substituímos 268 usando \;1402 = 2\cdot 567 + 268\;, logo 268 = 1402 - 2\cdot 567:
1 = 256\cdot(1402 - 2\cdot 567) -121\cdot 567 = 256\cdot 1402 -512\cdot 567 -121\cdot 567 = 256\cdot 1402 -633\cdot 567.

Passo 11

Finalmente substituímos 567 usando \;1969 = 1\cdot 1402 + 567\;, ou seja 567 = 1969 - 1\cdot 1402:
1 = 256\cdot 1402 -633\cdot(1969 - 1\cdot 1402) = 256\cdot 1402 -633\cdot 1969 +633\cdot 1402 = (256+633)\cdot 1402 -633\cdot 1969.
Somando os coeficientes de 1402 obtemos 256+633 = 889. Assim:
1 = 889\cdot 1402 - 633\cdot 1969.

Passo 12

Interpretação final: escrevemos \operatorname{mdc}(1402,1969) como combinação linear dos dois números. Aqui \operatorname{mdc}(1402,1969)=1 e os coeficientes inteiros são u=889 e v=-633. Sempre é bom checar substituindo: 889\cdot 1402 -633\cdot 1969 = 1 (confere).

Resposta

\operatorname{mdc}(1402,1969)=1=1402\cdot 889 + 1969\cdot (-633)

Exercícios relacionados