1. O mdc de dois números é 15. Na sua determinação pelo algoritmo de Euclides, encontramos os quocientes 3,1,2 e 4. Quais são os números?
    a) 540 e 180
    b) 540 e 385
    c) 720 e 195
    d) 620 e 165

Passo 1

O enunciado diz que dois números positivos a e b têm gcd(a,b)=15 e, ao aplicar o algoritmo de Euclides para calcular esse mdc, obtivemos os quocientes
q1=3, q2=1, q3=2, q4=4
Vamos usar a “volta” do algoritmo (back-substitution) para achar a e b.

Passo 2

Escrevemos as divisões sucessivas do algoritmo de Euclides com resto:
a = q1,b + r1, b = q2,r1 + r2, r1 = q3,r2 + r3, r2 = q4,r3 + 0,
sabendo que r3 = gcd(a,b)=15.

Passo 3

Começando de baixo para cima, calculamos
r2 = q4cdot r3 = 4cdot15 = 60,
r1 = q3cdot r2 + r3 = 2cdot60 + 15 = 135

Passo 4

Agora encontramos b e a de volta na cadeia de divisões:
b = q2cdot r1 + r2 = 1cdot135 + 60 = 195,
a = q1cdot b + r1 = 3cdot195 + 135 = 720

Resposta

c) 720 e 195