Para cada par de números naturais a e b dados abaixo, ache ( a, b ) e determine números inteiros x e y tais que a x+b y=(a, b).
637 e 3887

Passo 1

O enunciado pede duas coisas para os números naturais dados a=637 e b=3887: (1) achar (a,b), isto é, o máximo divisor comum de a e b; (2) determinar inteiros x e y tais que a x + b y = (a,b).
Informações dadas: a=637 e b=3887. Não vou resolver nada ainda — só organizei o que é pedido e o que foi dado.

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 \gcd(a,b) fazendo divisões sucessivas com resto: a cada passo escrevemos
r_{k-2} = q_k r_{k-1} + r_k,
onde r_{k-2} é o dividendo, r_{k-1} o divisor, q_k o quociente inteiro e r_k o resto com 0 \le r_k < r_{k-1}. Repetimos até obter resto zero; o último resto não nulo é o \gcd.
O algoritmo estendido faz a mesma sequência de divisões, mas guarda como cada resto é combinação linear de a e b; no final obtemos inteiros x,y tais que a x + b y = \gcd(a,b). Vou primeiro executar as divisões e depois fazer a substituição para achar x e y.

Passo 3

Executando o Algoritmo de Euclides para a=637 e b=3887. Colocamos sempre o maior primeiro; aqui b>a, então dividimos b por a.
Divisão 1:
3887 = 637\cdot 6 + 65,
porque 637\cdot 6 = 3822 e 3887-3822=65.
Divisão 2:
637 = 65\cdot 9 + 52,
porque 65\cdot 9 = 585 e 637-585=52.
Divisão 3:
65 = 52\cdot 1 + 13,
porque 52\cdot 1 = 52 e 65-52=13.
Divisão 4:
52 = 13\cdot 4 + 0.
Como o resto tornou-se 0, o último resto não nulo é 13. Portanto (637,3887)=13.

Passo 4

Agora o algoritmo estendido: vamos escrever o último resto não nulo 13 como combinação linear de 637 e 3887 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:
\begin{aligned} (1)\\ &65 &=&\\\ 3887 - 637\cdot 6,\\\ (2)\\ &52 &=&\\\ 637 - 65\cdot 9,\\\ (3)\\ &13 &=&\\\ 65 - 52\cdot 1. \end{aligned}
A ideia é eliminar os restos intermediários ( 65 e 52) substituindo as expressões (1) e (2) dentro de (3) até obter 13 em termos de 637 e 3887.

Passo 5

Primeira substituição: usar (2) dentro de (3) para eliminar 52. A igualdade (3) é
13 = 65 - 52\cdot 1.
Substituímos 52 por 637 - 65\cdot 9 (pela (2)):
\begin{aligned} 13 &= 65 - \big(637 - 65\cdot 9\big)\cdot 1\\\ &= 65 - 637 + 65\cdot 9\\\ &= 65\cdot(1+9) - 637\\\ &= 65\cdot 10 - 637. \end{aligned}
Ou seja,
13 = 65\cdot 10 - 637.

Passo 6

Segunda substituição: agora eliminar 65 usando (1). Da (1) temos 65 = 3887 - 637\cdot 6. Substituindo em 13 = 65\cdot 10 - 637:
\begin{aligned} 13 &= \big(3887 - 637\cdot 6\big)\cdot 10 - 637\\\ &= 3887\cdot 10 - 637\cdot 60 - 637\\\ &= 3887\cdot 10 - 637\cdot(60+1)\\\ &= 3887\cdot 10 - 637\cdot 61. \end{aligned}
Portanto chegamos à escrita de 13 como combinação linear de 637 e 3887:
13 = (-61)\cdot 637 + 10\cdot 3887.

Passo 7

Interpretação final e verificação (importante na prova): isto significa que podemos escolher x e y tais que
637\cdot x + 3887\cdot y = 13
tomando x=-61 e y=10. Vamos checar numericamente (fazendo as contas sem calculadora passo a passo, como você faria na prova):
637\cdot (-61) = - (637\cdot 61).
Calcule 637\cdot 60 = 38220 e some mais 637 para obter 637\cdot 61 = 38220 + 637 = 38857. Então 637\cdot(-61) = -38857.
Agora 3887\cdot 10 = 38870. Somando:
-38857 + 38870 = 13,
confirmando que a combinação está correta.

Resposta

(637,3887)=13
x=-61,\\ y=10

Exercícios relacionados