[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)=(102,1001)

Passo 1

O enunciado dá o par (a,b)=(102,1001) e pede que eu escreva a identidade de Bézout
\operatorname{mdc}(a,b)=a\,u+b\,v
encontrando inteiros u e v. Portanto, preciso:
  • calcular \operatorname{mdc}(102,1001);
  • encontrar inteiros u e v tais que \operatorname{mdc}(102,1001)=102\cdot u + 1001\cdot v.

Passo 2

Explicação rápida do método que vou usar (Algoritmo de Euclides estendido):
  • Primeiro aplicamos o Algoritmo de Euclides (divisões sucessivas) para obter o máximo divisor comum como o último resto não nulo.
  • Depois fazemos a “substituição para trás” (back-substitution) nas escritas das divisões para expressar esse resto final como combinação inteira dos números iniciais; isso nos dá os coeficientes u e v.
    Relembrando a divisão euclidiana: dados inteiros x,y com y>0, existe q,r tais que
x = yq + r,\qquad 0\le r<y.

Passo 3

Faço as divisões sucessivas entre 1001 e 102:
1001 = 102\cdot 9 + 83.
102 = 83\cdot 1 + 19.
83 = 19\cdot 4 + 7.
19 = 7\cdot 2 + 5.
7 = 5\cdot 1 + 2.
5 = 2\cdot 2 + 1.
2 = 1\cdot 2 + 0.

Passo 4

O último resto não nulo é 1, portanto
\operatorname{mdc}(102,1001)=1.
Agora vamos expressar 1 como combinação inteira de 102 e 1001 usando as igualdades acima (back-substitution).

Passo 5

Começo a partir da penúltima igualdade (onde apareceu o resto 1):
1 = 5 - 2\cdot 2.

Passo 6

Usando 2 = 7 - 5\cdot 1 (da divisão anterior), substituo na expressão de 1:
1 = 5 - 2\cdot(7 - 5) = 5 - 2\cdot 7 + 2\cdot 5 = 3\cdot 5 - 2\cdot 7.

Passo 7

Usando 5 = 19 - 7\cdot 2, substituo na expressão anterior:
1 = 3\cdot(19 - 7\cdot 2) - 2\cdot 7 = 3\cdot 19 - 6\cdot 7 - 2\cdot 7 = 3\cdot 19 - 8\cdot 7.

Passo 8

Usando 7 = 83 - 19\cdot 4, substituo:
1 = 3\cdot 19 - 8\cdot(83 - 19\cdot 4) = 3\cdot 19 - 8\cdot 83 + 32\cdot 19.
Junto os termos em 19:
1 = (3+32)\cdot 19 - 8\cdot 83 = 35\cdot 19 - 8\cdot 83.

Passo 9

Usando 19 = 102 - 83\cdot 1, substituo:
1 = 35\cdot(102 - 83) - 8\cdot 83 = 35\cdot 102 - 35\cdot 83 - 8\cdot 83.
Junto os termos em 83:
1 = 35\cdot 102 - 43\cdot 83.

Passo 10

Usando 83 = 1001 - 102\cdot 9 (da primeira divisão), substituo:
1 = 35\cdot 102 - 43\cdot(1001 - 102\cdot 9) = 35\cdot 102 - 43\cdot 1001 + 387\cdot 102.
Junto os termos em 102:
1 = (35 + 387)\cdot 102 - 43\cdot 1001 = 422\cdot 102 - 43\cdot 1001.

Resposta

\operatorname{mdc}(102,1001)=102\cdot 422 + 1001\cdot (-43)

Exercícios relacionados