Como é que podemos encontrar o máximo divisor comum de dois números sem ter de fazer a lista de todos os seus divisores?
Antes de responder a esta pergunta, vamos
começar por ver alguns casos particulares e uma propriedade importante.
Quais são os divisores
comuns de \(a\)
e \(b\)
quando \(a\)
é múltiplo de \(b\)?
Qual é o
máximo divisor comum de \(a\)
e \(b\)
quando \(a\)
é múltiplo de \(b\)?
Se \(a=b+c\),
qual é a relação
entre os divisores comuns de \(a\)
e \(b\)
e os divisores comuns de \(b\)
e \(c\)?
Com as respostas a estas perguntas podemos finalmente ver o algoritmo de Euclides para encontrar o máximo divisor comum de dois números.