Encontrar, usando o algoritmo de Euclides, o máximo divisor comum dos seguintes pares de números:
24573 e 1387

Passo 1

Resumo do enunciado: a gente precisa achar o máximo divisor comum (MDC) de 24573 e 1387 usando o algoritmo de Euclides.
Conteúdo da matéria: teoria do máximo divisor comum e algoritmo de Euclides (que usa divisão com resto).
O que vamos precisar: saber fazer divisões inteiras para obter quociente e resto, e usar a propriedade
gcd(a, b) = gcd(b, r)
onde é o resto de dividido por , até o resto ser zero.

Passo 2

Começa dividindo o número maior pelo menor:
24573 = 1387 times 17 + 994
Aqui o quociente é 17 e o resto é 994. Pelo algoritmo,
gcd(24573, 1387) = gcd(1387, 994)

Passo 3

Agora dividimos 1387 por 994:
1387 = 994 times 1 + 393
Quociente 1, resto 393. Logo
gcd(1387, 994) = gcd(994, 393)

Passo 4

Dividindo 994 por 393:
994 = 393 times 2 + 208
Quociente 2, resto 208. Então
gcd(994, 393) = gcd(393, 208)

Passo 5

Dividindo 393 por 208:
393 = 208 times 1 + 185
Quociente 1, resto 185. Logo
gcd(393, 208) = gcd(208, 185)

Passo 6

Dividindo 208 por 185:
208 = 185 times 1 + 23
Quociente 1, resto 23. Então
gcd(208, 185) = gcd(185, 23)

Passo 7

Dividindo 185 por 23:
185 = 23 times 8 + 1
Quociente 8, resto 1. Assim
gcd(185, 23) = gcd(23, 1)

Passo 8

Dividindo 23 por 1:
23 = 1 times 23 + 0
O resto ficou zero, então a gente para por aqui. O último resto não nulo é 1.

Resposta

O máximo divisor comum de 24573 e 1387 é 1.

Exercícios relacionados