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 5913 e 7592.
Encontre, com o algoritmo euclidiano, o m.d.c. de 5913 e 7592.
Passo 1
O enunciado pede para encontrar o máximo divisor comum (m.d.c.) dos números
e
usando o algoritmo euclidiano. Informações dadas:
- Os dois números são
e . - Pedido: calcular o m.d.c. desses dois inteiros positivos.
Passo 2
Vou explicar a ideia que vamos usar (sem resolver ainda). A regra básica é a seguinte (Algoritmo Euclidiano / Teorema da divisão):
- Para inteiros positivos
e com , existe um quociente e resto tais que
- Propriedade crucial:
. Em palavras: o máximo divisor comum entre e é igual ao máximo divisor comum entre e o resto . Isso permite reduzir o problema repetindo a divisão com pares menores até que o resto seja zero. - Quando um resto
é zero, o divisor usado nessa etapa é o m.d.c. final.
Breve justificativa (intuição simples, sem formalidade pesada): todo divisor comum de
e
também divide
, e todo divisor comum de
e
divide
. Assim os conjuntos de divisores comuns coincidem e, portanto, seus maiores elementos também coincidem.
Passo 3
Aplicamos a primeira divisão (o maior é
, o menor é
). Calculamos quociente e resto:
porque
e
. Aqui o resto é
(e
, está correto).
Passo 4
Pelo que escrevemos antes,
. Agora dividimos
por
:
pois
e
. O resto é
.
Passo 5
Continuamos:
. Dividindo
por
:
porque
e
. O resto é
.
Passo 6
Seguimos:
. Dividindo
por
:
já que
e
. O resto é
.
Passo 7
Agora:
. Dividimos
por
:
pois
exatamente, então o resto é
.
Passo 8
Terminamos o algoritmo porque obtivemos resto
. A regra diz que o último divisor não nulo é o m.d.c. Assim o m.d.c. é o último resto não nulo, que aqui é
. Logo
Passo 9
(Comentário prático e dica de prova) O que fizemos foi aplicar repetidamente a divisão com resto e usar a igualdade
até o resto zero. Em prova: execute cada divisão com cuidado, anote quocientes e restos e pare quando o resto for
. O último divisor não nulo é a resposta. Se quiser certificar-se, pode também expressar o m.d.c. como combinação linear (algoritmo de Euclides estendido) — aqui obtemos:
o que confirma que
divide ambos e, sendo o último divisor do processo, é o maior que o faz.