Resolva
Calcule or mdc
Calcule or mdc
Passo 1
O enunciado pede para calcular o máximo divisor comum (mdc) entre os números
e
.
Informações dadas:
Informações dadas:
- Os dois inteiros são
e .
O que se pede: - Determinar
, ou seja, o maior inteiro positivo que divide simultaneamente e .
Passo 2
Idéia da técnica que vamos usar (explicação didática): o algoritmo de Euclides.
Fato importante (que vale lembrar e que será usado várias vezes): se dividimos por
e obtemos resto
, então
Fato importante (que vale lembrar e que será usado várias vezes): se dividimos
Isso acontece porque qualquer divisor comum de
e
também divide
, e recíproco. Na prática, aplicamos sucessivas divisões com resto até obter resto zero; o último resto não nulo é o
.
Passo 3
Primeira divisão: dividir
por
. Calcule o quociente inteiro e o resto:
pois
e
.
Passo 4
Pelo princípio anterior,
Passo 5
Segunda divisão: dividir
por
:
pois
e
.
Passo 6
Atualizando,
Passo 7
Terceira divisão: dividir
por
:
pois
e
.
Passo 8
Atualizando,
Passo 9
Quarta divisão: dividir
por
:
O resto é zero, portanto o algoritmo termina aqui.
Passo 10
Conclusão do algoritmo de Euclides: quando se obtém resto
, o último resto não nulo (aqui
) é o
. Podemos então afirmar que
Verificação rápida (racicínio): ambos
e
são pares, logo pelo menos
divide ambos; pelo algoritmo não existe divisor maior que divide ambos, então
é o máximo divisor comum.