O mdc entre dois números naturais
e
pode ser facilmente calculado por meio do algoritmo de Euclides. Faça uma pesquisa e descubra como funciona esse algoritmo.
Passo 1
O enunciado pede para entender como o Algoritmo de Euclides calcula o maior divisor comum (mdc) de dois naturais
e
. Vamos estudar a ideia de usar divisões sucessivas e o fato de que o mdc não muda quando substituímos o par
por
, onde
é o resto da divisão de
por
.
Passo 2
Começamos usando o Teorema da Divisão: dados
e
com
, existem inteiros únicos
(quociente) e
(resto) tais que
Aqui
é o resto da divisão de
por
.
Passo 3
A chave do algoritmo é a propriedade
Isto ocorre porque qualquer divisor comum de
e
também divide
, e vice-versa.
Passo 4
Com essa propriedade, definimos o procedimento:
- Dados
e , com , calculamos o resto de dividido por . - Se
, então e o algoritmo para. - Caso contrário, substituímos
por e repetimos o passo 1.
Passo 5
Em forma de pseudocódigo, fica assim:
Quando
, o valor de
é o
inicial.
Resposta
O Algoritmo de Euclides determina
repetindo o cálculo do resto
e trocando
até que o novo
seja zero. Nesse ponto, o valor de
é justamente o maior divisor comum dos valores iniciais.