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

Passo 1

Beleza, o enunciado pede pra gente descobrir o máximo divisor comum (MDC) de 42516 e 97421 usando o algoritmo de Euclides. Isso faz parte de Teoria dos Números, mais especificamente de divisibilidade e cálculo de MDC. O que vamos usar é o princípio de que
gcd(a,b) = gcd(b,,r)
onde é o resto da divisão de por . Então vamos dividir, anotar o resto e repetir até o resto dar zero.

Passo 2

Começamos dividindo o maior pelo menor:
97421 = 2 times 42516 + 12389
Então .

Passo 3

Agora dividimos 42516 por 12389:
42516 = 3 times 12389 + 5349
Logo .

Passo 4

Continuando:
12389 = 2 times 5349 + 1691
Portanto .

Passo 5

Próxima divisão:
5349 = 3 times 1691 + 276
Então .

Passo 6

Seguindo:
1691 = 6 times 276 + 35
Logo .

Passo 7

Vamos adiante:
276 = 7 times 35 + 31
Então .

Passo 8

Mais uma:
35 = 1 times 31 + 4
Assim .

Passo 9

Continuando:
31 = 7 times 4 + 3
Portanto .

Passo 10

Quase lá:
4 = 1 times 3 + 1
Logo .

Passo 11

Finalmente:
3 = 3 times 1 + 0
Quando o resto chega em zero, a gente para. O último divisor não nulo é 1, ou seja, .

Resposta

O máximo divisor comum de 42516 e 97421 é 1.

Exercícios relacionados