Encontre o máximo divisor comum dos seguintes inteiros e sua expressão como combinação linear desses inteiros pelo Algoritmo de Euclides:
(a) 232 e 136;

Passo 1

O enunciado pede duas coisas para os inteiros dados: (i) o máximo divisor comum (MDC) de \;232 e \;136; (ii) expressar esse MDC como combinação linear desses inteiros, isto é, encontrar inteiros x e y tais que
\gcd(232,136)=x\cdot232+y\cdot136.
As informações dadas são apenas os dois números \;232 e \;136.

Passo 2

Vou usar o Algoritmo de Euclides. A ideia básica (fórmula de divisão) é: para inteiros a e b>0 existem inteiros q e r com 0\le r<b tais que
a = b\cdot q + r.
O ponto importante é que \gcd(a,b)=\gcd(b,r). Repetindo divisões sucessivas até o resto ser zero, o último resto não nulo é o MDC.

Passo 3

Começo aplicando a divisão com a=232 e b=136:
232 = 136\cdot 1 + 96.
Aqui o quociente é 1 e o resto é 96.

Passo 4

Agora divido 136 por 96:
136 = 96\cdot 1 + 40.
Quociente 1, resto 40.

Passo 5

Divido 96 por 40:
96 = 40\cdot 2 + 16.
Quociente 2, resto 16.

Passo 6

Divido 40 por 16:
40 = 16\cdot 2 + 8.
Quociente 2, resto 8.

Passo 7

Divido 16 por 8:
16 = 8\cdot 2 + 0.
Aqui o resto é 0, então o último resto não nulo é 8. Portanto
\gcd(232,136)=8.

Passo 8

Agora vamos obter a combinação linear (algoritmo extensivo de Euclides): voltamos nas igualdades acima e expressamos 8 como combinação linear de 232 e 136. Reescrevo as igualdades relevantes (peguei estes dados das divisões feitas acima):
\begin{aligned} 232 &= 136\cdot 1 + 96,\\\\ 136 &= 96\cdot 1 + 40,\\\\ 96 &= 40\cdot 2 + 16,\\\\ 40 &= 16\cdot 2 + 8. \end{aligned}

Passo 9

Começo isolando o resto 8 da última linha:
8 = 40 - 16\cdot 2.

Passo 10

Substituo 16 usando a terceira linha onde 16 = 96 - 40\cdot 2. Assim
\begin{aligned} 8 &= 40 - 2\cdot(96 - 2\cdot40)\\\ &= 40 - 2\cdot96 + 4\cdot40\\\ &= 5\cdot40 - 2\cdot96. \end{aligned}

Passo 11

Substituo 40 usando a segunda linha onde 40 = 136 - 96. Então
\begin{aligned} 8 &= 5\cdot(136 - 96) - 2\cdot96\\\ &= 5\cdot136 - 5\cdot96 - 2\cdot96\\\ &= 5\cdot136 - 7\cdot96. \end{aligned}

Passo 12

Substituo 96 usando a primeira linha onde 96 = 232 - 136. Assim
\begin{aligned} 8 &= 5\cdot136 - 7\cdot(232 - 136)\\\ &= 5\cdot136 - 7\cdot232 + 7\cdot136\\\ &= -7\cdot232 + 12\cdot136. \end{aligned}

Passo 13

Verificação rápida (confirmação): calculemos -7\cdot232 + 12\cdot136:
-7\cdot232 + 12\cdot136 = -1624 + 1632 = 8,
confirmando que a combinação está correta.

Resposta

\gcd(232,136)=8
8 = -7\cdot232 + 12\cdot136

Exercícios relacionados