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

Passo 1

Beleza, o enunciado quer que a gente ache o máximo divisor comum (MDC) entre 8374 e 24517 usando o algoritmo de Euclides. Esse conteúdo é sobre divisão com resto e a propriedade
gcd(a,b) = gcd(b,,r),
onde é o resto de dividido por . Para resolver, a gente vai fazer várias divisões, anotar os restos e parar quando der resto zero.

Passo 2

Começamos dividindo o maior pelo menor:
24517 = 2 times 8374 + 7769
Aqui o quociente é 2 e o resto é 7769. Então
gcd(24517,8374) = gcd(8374,7769)

Passo 3

Agora dividimos 8374 por 7769:
8374 = 1 times 7769 + 605
Resto 605, logo
gcd(8374,7769) = gcd(7769,605)

Passo 4

Dividindo 7769 por 605:
7769 = 12 times 605 + 509
Resto 509, então
gcd(7769,605) = gcd(605,509)

Passo 5

Agora 605 dividido por 509:
605 = 1 times 509 + 96
Resto 96, fica
gcd(605,509) = gcd(509,96)

Passo 6

509 dividido por 96:
509 = 5 times 96 + 29
Resto 29, e
gcd(509,96) = gcd(96,29)

Passo 7

96 dividido por 29:
96 = 3 times 29 + 9
Resto 9, então
gcd(96,29) = gcd(29,9)

Passo 8

29 dividido por 9:
29 = 3 times 9 + 2
Resto 2, logo
gcd(29,9) = gcd(9,2)

Passo 9

9 dividido por 2:
9 = 4 times 2 + 1
Resto 1, assim
gcd(9,2) = gcd(2,1)

Passo 10

2 dividido por 1:
2 = 2 times 1 + 0
Resto zero significa que a gente para aqui, e o último resto não nulo é 1.

Resposta

O máximo divisor comum de 8374 e 24517 é .

Exercícios relacionados