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.
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:
A pergunta é: qual é
?
Passo 2
Antes de começar, vamos lembrar direitinho a ideia do algoritmo euclidiano (passo a passo, explicadinho como num exame). Para dois inteiros
e
com
, faz-se divisões sucessivas do tipo
depois
e assim por diante, até aparecer um resto zero; o último divisor não-nulo é
.
Fato útil para três números: para quaisquer inteiros
,
Portanto podemos primeiro calcular
e depois calcular
.
Pequeno exemplo para fixar a ideia (pra você se animar):
. Fazendo
logo
. Viu como é só dividir até o resto zero?
Passo 3
Vamos aplicar o algoritmo a
e
(escolhi essa ordem porque
). Primeiro passo da divisão:
ou seja,
e
(confirmar que
).
Passo 4
Continuamos dividindo o anterior divisor pelo resto obtido:
então
e
.
Passo 5
Próxima divisão:
então
.
Passo 6
Continuando:
então
.
Passo 7
Mais uma:
então
.
Passo 8
E finalmente:
Como o resto é
, o último divisor não-nulo é
. Portanto
Passo 9
Agora usamos esse resultado com o terceiro número. Calculamos
. Começamos dividindo
por
:
pois
e
.
Passo 10
Em seguida:
O resto é
, então o último divisor não-nulo é
. Logo
Passo 11
Como
e
, usando a propriedade para três números concluímos: