Use o algoritmo de Euclides para calcular d=mdc(a, b), e encontrar r, s in Z tais que d=r a+s b.
a=412, b=32, ; a=780, b=150, ; a=10672, b=414

Passo 1

Neste exercício vamos usar o algoritmo de Euclides estendido para calcular o máximo divisor comum d=gcd(a,b) e encontrar inteiros r,s tais que d = r a + s b. Vamos aplicar isso a três pares (a,b).

Passo 2

Para a=412 e b=32, aplicamos o algoritmo de Euclides:
412 = 32 cdot 12 + 28
32 = 28 cdot 1 + 4
28 = 4 cdot 7 + 0
Logo gcd(412,32)=4.

Passo 3

Para obter r e s, começamos do último resto não nulo 4 e voltamos nas divisões:
4 = 32 - 28 cdot 1
Substituindo 28 = 412 - 32 cdot 12:
4 = 32 - (412 - 32 cdot 12) = -412 + 32 cdot 13
Dessa forma 4 = (-1)cdot 412 + 13cdot 32, logo r=-1, s=13.

Passo 4

Para a=780 e b=150, aplicamos o algoritmo de Euclides:
780 = 150 cdot 5 + 30
150 = 30 cdot 5 + 0
Logo gcd(780,150)=30.

Passo 5

Para encontrar r e s, note que
30 = 780 - 150 cdot 5
Então 30 = 1cdot 780 + (-5)cdot 150, logo r=1, s=-5.

Passo 6

Para a=10672 e b=414, aplicamos o algoritmo de Euclides:
10672 = 414 cdot 25 + 322
414 = 322 cdot 1 + 92
322 = 92 cdot 3 + 46
92 = 46 cdot 2 + 0
Logo gcd(10672,414)=46.

Passo 7

Para os coeficientes, começamos de 46:
46 = 322 - 92 cdot 3
Substituindo 92 = 414 - 322:
46 = 322 - (414 - 322) cdot 3 = 4cdot 322 - 3cdot 414
Substituindo 322 = 10672 - 414 cdot 25:
46 = 4(10672 - 414cdot 25) - 3cdot 414 = 4cdot10672 - 103cdot414
Portanto r=4, s=-103.

Resposta

Para a=412, b=32: d=4, r=-1, s=13. Para a=780, b=150: d=30, r=1, s=-5. Para a=10672, b=414: d=46, r=4, s=-103.

Exercícios relacionados