Calcule r e s in Z tais que M.D.C. a, b=r a+s b nos seguintes casos:
a=180 ; b=252.

Passo 1

O enunciado pede para encontrar inteiros r e s tais que o máximo divisor comum de a e b se escreva como combinação linear
gcd(a,b)=r,a + s,b
com a=180 e b=252. Vamos usar o algoritmo de Euclides estendido, que consiste em aplicar o algoritmo de Euclides para calcular gcd(180,252) e, em seguida, fazer o “back-substitution” para expressar esse valor como combinação linear de 180 e 252.

Passo 2

Aplicamos o algoritmo de Euclides para encontrar gcd(180,252):
252 = 1 times 180 + 72,
180 = 2 times 72 + 36,
72 = 2 times 36 + 0
Como o resto zera em seguida, temos
gcd(180,252) = 36

Passo 3

Agora escrevemos 36 em termos dos restos anteriores. Da segunda linha:
36 = 180 - 2 times 72

Passo 4

Substituímos 72 pela expressão da primeira linha, onde
72 = 252 - 1 times 180
Logo,
36 = 180 - 2,(252 - 1cdot 180)
= 180 -2cdot 252 +2cdot 180
= 3cdot 180 -2cdot 252
Portanto, a combinação linear desejada é
gcd(180,252)=3cdot 180 +(-2)cdot 252

Resposta

r = 3, s = -2.

Exercícios relacionados