O algoritmo euclidiano, processo para se achar o máximo divisor comum (m.d.c.) de dois números inteiros, tem esse nome porque se encontra no início do Livro VII dos Elementos de Euclides, embora o processo em si sem dúvida fosse conhecido muito tempo antes. Esse algoritmo se encontra nos fundamentos de vários progressos da matemática moderna. Enunciado em forma de regra, é o seguinte: Divida o maior dos dois números inteiros positivos pelo menor e então divida o divisor pelo resto. Continue esse processo de dividir o último divisor pelo último resto, até que a divisão seja exata. O divisor final é o m.d.c. procurado.
Encontre, com o algoritmo euclidiano, o m.d.c. de 1827, 2523 e 3248.

Passo 1

O enunciado pede para encontrar o máximo divisor comum (m.d.c.) dos três inteiros fornecidos. Os dados são:
  • 1827
  • 2523
  • 3248
A pergunta é: qual é \text{m.d.c.}(1827,2523,3248)?

Passo 2

Antes de começar, vamos lembrar direitinho a ideia do algoritmo euclidiano (passo a passo, explicadinho como num exame). Para dois inteiros a e b com a\ge b>0, faz-se divisões sucessivas do tipo
a = q_1 b + r_1,\quad 0\le r_1<b,
depois
b = q_2 r_1 + r_2,\quad 0\le r_2<r_1,
e assim por diante, até aparecer um resto zero; o último divisor não-nulo é \gcd(a,b).
Fato útil para três números: para quaisquer inteiros x,y,z,
\gcd(x,y,z)=\gcd(\gcd(x,y),z).
Portanto podemos primeiro calcular \gcd(2523,1827) e depois calcular \gcd(\text{resultado},3248).
Pequeno exemplo para fixar a ideia (pra você se animar): \gcd(48,18). Fazendo
48=2\cdot18+12,\qquad 18=1\cdot12+6,\qquad 12=2\cdot6+0,
logo \gcd(48,18)=6. Viu como é só dividir até o resto zero?

Passo 3

Vamos aplicar o algoritmo a \,2523 e \,1827 (escolhi essa ordem porque \,2523>1827). Primeiro passo da divisão:
2523 = 1\cdot1827 + 696,
ou seja, q_1=1 e r_1=696 (confirmar que 0\le696<1827).

Passo 4

Continuamos dividindo o anterior divisor pelo resto obtido:
1827 = 2\cdot696 + 435,
então q_2=2 e r_2=435.

Passo 5

Próxima divisão:
696 = 1\cdot435 + 261,
então r_3=261.

Passo 6

Continuando:
435 = 1\cdot261 + 174,
então r_4=174.

Passo 7

Mais uma:
261 = 1\cdot174 + 87,
então r_5=87.

Passo 8

E finalmente:
174 = 2\cdot87 + 0.
Como o resto é 0, o último divisor não-nulo é 87. Portanto
\gcd(2523,1827)=87.

Passo 9

Agora usamos esse resultado com o terceiro número. Calculamos \gcd(87,3248). Começamos dividindo 3248 por 87:
3248 = 37\cdot87 + 29,
pois 37\cdot87=3219 e 3248-3219=29.

Passo 10

Em seguida:
87 = 3\cdot29 + 0.
O resto é 0, então o último divisor não-nulo é 29. Logo
\gcd(87,3248)=29.

Passo 11

Como \gcd(2523,1827)=87 e \gcd(87,3248)=29, usando a propriedade para três números concluímos:
\gcd(1827,2523,3248)=29.

Resposta

\text{m.d.c.}(1827,2523,3248)=29

Exercícios relacionados