Encontre o máximo divisor comum de cada par de inteiros dados.
;
Passo 1
O enunciado pede: encontrar o máximo divisor comum (MDC) do par de inteiros dados.
As informações fornecidas são os dois inteiros:
As informações fornecidas são os dois inteiros:
Passo 2
O que é o máximo divisor comum? Vou explicar de forma bem direta.
O máximo divisor comum de dois inteiros positivos é o maior inteiro positivo que divide ambos sem deixar resto. Em notação usamos para denotar o MDC de
e
.
Exemplo simples: porque
é o maior número que divide
e
.
O máximo divisor comum de dois inteiros positivos é o maior inteiro positivo que divide ambos sem deixar resto. Em notação usamos
Exemplo simples:
Passo 3
Método escolhido: algoritmo de Euclides (rápido e confiável). Vou explicar a ideia: se
e
são inteiros com
, dividimos
por
e obtemos um quociente e resto:
Qualquer divisor comum de
e
também divide
. Portanto
Repetimos essa divisão até o resto ser zero; o último resto não nulo é o
. É um procedimento muito prático para fazer na prova sem fatorar nada.
Passo 4
Aplicando o algoritmo de Euclides aos números dados. Primeiro, ordeno para ter o maior primeiro:
,
. Faço a divisão inteira:
Aqui o resto é
. Pelo algoritmo,
Agora divido
por
:
O resto agora é
. O último resto não nulo foi
. Então, pelo algoritmo, o MDC é
.
Passo 5
Verificação por fatoração (checar é uma boa prática): fatoro os números em primos.
Os fatores primos em comum são apenas
. O produto dos fatores comuns (com menor expoente) é
. Isso confirma o resultado obtido pelo algoritmo de Euclides.
Passo 6
Resumo didático rápido para a prova: usar o algoritmo de Euclides é geralmente mais rápido — faça divisões sucessivas até obter resto zero; o último resto não nulo é o MDC. Como checagem, se os números forem pequenos, a fatoração em primos também funciona bem.