[Revisão] Use o algoritmo de Euclides para calcular o
nos pares abaixo, escrevendo todas as divisões sucessivas:
Passo 1
O enunciado pede para calcular o
usando o algoritmo de Euclides, escrevendo todas as divisões sucessivas.
Informações dadas: os dois números inteiros positivos e
.
Objetivo: encontrar o maior divisor comum (mdc) entre e
.
Informações dadas: os dois números inteiros positivos
Objetivo: encontrar o maior divisor comum (mdc) entre
Passo 2
Explicação do método (aula rápida e amigável).
O algoritmo de Euclides baseia-se na divisão com resto: se temos dois inteiros e
com
, podemos escrever
O algoritmo de Euclides baseia-se na divisão com resto: se temos dois inteiros
onde
é o quociente inteiro e
é o resto com
. Uma propriedade chave é que
Assim repetimos trocando os pares até obter resto zero; o último resto não nulo é o
.
Em palavras: o resto carrega toda a informação sobre fatores comuns, então podemos reduzir o problema sucessivamente até sobrar um divisor exato.
Em palavras: o resto carrega toda a informação sobre fatores comuns, então podemos reduzir o problema sucessivamente até sobrar um divisor exato.
Passo 3
Primeira divisão: dividimos
por
.
Aqui
e
. Verificação do resto:
.
Passo 4
Segunda divisão: agora dividimos
por
.
Aqui
e
. Verificação:
.
Passo 5
Terceira divisão: dividimos
por
.
Aqui
e
. Verificação:
e
.
Passo 6
Quarta divisão: dividimos
por
.
Aqui o resto é zero, então paramos. Pelo algoritmo de Euclides, o último resto não nulo é o
, ou seja
.
Passo 7
Checagem final e interpretação didática.
Verificamos que divide ambos:
Verificamos que
logo
é um divisor comum. Como pelo algoritmo obtivemos resto zero após usar
, não existe divisor comum maior — portanto é o máximo.
Dica prática para a prova: faça cada divisão com cuidado, escreva o quociente e o resto; quando o resto chegar a zero, o último resto não nulo é a resposta. Respire fundo e avance etapa a etapa — funciona sempre!
Dica prática para a prova: faça cada divisão com cuidado, escreva o quociente e o resto; quando o resto chegar a zero, o último resto não nulo é a resposta. Respire fundo e avance etapa a etapa — funciona sempre!