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

Passo 1

Beleza, o enunciado pede pra gente achar o máximo divisor comum (MDC) de 4276 e 1234 usando o algoritmo de Euclides. Isso faz parte de Teoria dos Números, e pra resolver vamos usar a ideia de que, em cada passo, a gente divide o maior pelo menor, guarda o resto e repete até o resto ser zero.

Passo 2

Primeiro, lembra do algorítmo de Euclides: se você tem dois números a = b times q + r, e com , você faz
onde é o quociente inteiro e é o resto ( ). Depois você troca e repete até . O MDC é o último não nulo.

Passo 3

Vamos lá: 4276 = 1234 times 3 + 574, , . Dividindo:
porque e .
Então agora .

Passo 4

Agora divide 1234 = 574 times 2 + 86, por :
pois e .
Fica .

Passo 5

Próxima:
574 = 86 times 6 + 58,
já que e .
Agora .

Passo 6

Continuando:
86 = 58 times 1 + 28,
porque e .
Vai pra .

Passo 7

Mais uma:
58 = 28 times 2 + 2,
já que e .
Então .

Passo 8

Agora:
28 = 2 times 14 + 0
O resto deu zero, então a gente parou. Nesse ponto, o divisor atual é o MDC.

Resposta

O máximo divisor comum de 4276 e 1234 é 2.

Exercícios relacionados