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.

Passo 1

O enunciado pede para encontrar o máximo divisor comum (m.d.c.) dos números 5913 e 7592 usando o algoritmo euclidiano. Informações dadas:
  • Os dois números são 5913 e 7592.
  • 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 a e b com a\ge b, existe um quociente q e resto r tais que
a = bq + r,\qquad 0 \le r < b.
  • Propriedade crucial: \gcd(a,b)=\gcd(b,r). Em palavras: o máximo divisor comum entre a e b é igual ao máximo divisor comum entre b e o resto r. Isso permite reduzir o problema repetindo a divisão com pares menores até que o resto seja zero.
  • Quando um resto r é zero, o divisor usado nessa etapa é o m.d.c. final.
Breve justificativa (intuição simples, sem formalidade pesada): todo divisor comum de a e b também divide r=a-bq, e todo divisor comum de b e r divide a=bq+r. Assim os conjuntos de divisores comuns coincidem e, portanto, seus maiores elementos também coincidem.

Passo 3

Aplicamos a primeira divisão (o maior é 7592, o menor é 5913). Calculamos quociente e resto:
7592 = 5913\cdot 1 + 1679,
porque 5913\cdot 1 = 5913 e 7592-5913=1679. Aqui o resto é 1679 (e 0\le 1679<5913, está correto).

Passo 4

Pelo que escrevemos antes, \gcd(7592,5913)=\gcd(5913,1679). Agora dividimos 5913 por 1679:
5913 = 1679\cdot 3 + 876,
pois 1679\cdot 3 = 5037 e 5913-5037=876. O resto é 876.

Passo 5

Continuamos: \gcd(5913,1679)=\gcd(1679,876). Dividindo 1679 por 876:
1679 = 876\cdot 1 + 803,
porque 876\cdot 1=876 e 1679-876=803. O resto é 803.

Passo 6

Seguimos: \gcd(1679,876)=\gcd(876,803). Dividindo 876 por 803:
876 = 803\cdot 1 + 73,
já que 803\cdot 1=803 e 876-803=73. O resto é 73.

Passo 7

Agora: \gcd(876,803)=\gcd(803,73). Dividimos 803 por 73:
803 = 73\cdot 11 + 0,
pois 73\cdot 11=803 exatamente, então o resto é 0.

Passo 8

Terminamos o algoritmo porque obtivemos resto 0. 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 é 73. Logo
\gcd(5913,7592)=73.

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 \gcd(a,b)=\gcd(b,r) até o resto zero. Em prova: execute cada divisão com cuidado, anote quocientes e restos e pare quando o resto for 0. 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:
73 = 9\cdot 5913 - 7\cdot 7592,
o que confirma que 73 divide ambos e, sendo o último divisor do processo, é o maior que o faz.

Resposta

\gcd(5913,7592)=73

Exercícios relacionados