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

Passo 1

Beleza, o enunciado pede pra gente achar o máximo divisor comum (mdc) de 35262 e 12753 usando o algoritmo de Euclides. O conteúdo aqui é justamente o algoritmo de Euclides, que se baseia em dividir sucessivamente dois números, anotando quociente e resto, e usar a propriedade
gcd(a,b)=gcd(b,r),
onde é o resto da divisão de por . Para resolver, só precisamos saber fazer essas divisões e repetir até o resto ser zero.

Passo 2

Primeira divisão: dividimos 35262 por 12753.
35262 = 12753 times 2 + 9756
Aqui o quociente é 2 e o resto é 9756. Pela lógica do Euclides, agora a gente troca o par por .

Passo 3

Agora dividimos 12753 por 9756.
12753 = 9756 times 1 + 2997
Quociente 1, resto 2997. O par vira .

Passo 4

Dividimos 9756 por 2997.
9756 = 2997 times 3 + 765
Quociente 3, resto 765. Seguimos com .

Passo 5

Dividimos 2997 por 765.
2997 = 765 times 3 + 702
Quociente 3, resto 702. Agora é .

Passo 6

Dividimos 765 por 702.
765 = 702 times 1 + 63
Quociente 1, resto 63. Fica .

Passo 7

Dividimos 702 por 63.
702 = 63 times 11 + 9
Quociente 11, resto 9. Agora é .

Passo 8

Dividimos 63 por 9.
63 = 9 times 7 + 0
Quociente 7, resto 0. Quando o resto é zero, paramos: o último resto não-nulo (que é 9) é o nosso mdc.

Resposta

O máximo divisor comum de 35262 e 12753 é 9.

Exercícios relacionados