Máximo divisor comum
O máximo divisor comum de dois números inteiros é o número que divide os dois números sem deixar resto e, ao mesmo tempo, não existe nenhum outro número maior que também divida os dois números sem deixar resto.
Como exemplo, tomemos os números 24 e 32. Qual é o máximo divisor comum deles? Procuramos, em primeiro lugar, um número que divida os dois números.
- Por exemplo, o número 12 divide o número 24, mas não divide o número 32, porque 32 / 12 é igual a 2,666…, que não é um número inteiro. Logo, o número 12 não pode ser o máximo divisor comum dos números 24 e 32.
- E o número 4? Ele divide os dois números, 24 / 4 é igual a 6 e 32 / 4 é igual a 8. O número 4 é, portanto, o nosso primeiro candidato. Existe algum número maior que divida os dois números?
- O número 8 divide tanto o número 24 quanto o número 32 e, ao mesmo tempo, é maior que o número 4.
- Não existe nenhum outro número maior que 8 que divida os dois números. O número 8 é, portanto, o máximo divisor comum dos números 24 e 32.
Algoritmo de Euclides para encontrar o máximo divisor comum
Existe um modo relativamente simples de encontrar o máximo divisor comum de dois números: o algoritmo de Euclides. Suponha que tenhamos no começo dois números x e y para os quais queremos encontrar o máximo divisor comum. Como exemplo, vamos tentar com os números x = 50 e y = 35. Então procedemos assim:
- Dividimos x / y e guardamos o resto da divisão. Anotamos esse resto como z. Para o nosso exemplo, obtemos 50 / 35, que nos dá o resto z = 15.
- Agora trocamos as variáveis: guardamos na variável x o valor de y e guardamos em y o valor de z. Descartamos o valor original de x. Depois desse passo, obtemos x = 35 e y = 15.
- Agora vemos se y é igual a zero. Se for, o máximo divisor comum é o número x. Como y não é igual a zero, continuamos e repetimos todo o procedimento novamente a partir do primeiro item.
- Dividimos novamente x / y, isto é, dividimos 35 / 15, o que nos dá o resto da divisão z = 5.
- Fazemos a troca das variáveis, ou seja, obtemos x = 15 e y = 5. Como y não é igual a zero, continuamos.
- Dividimos x / y, isto é, dividimos 15 / 5. O resto da divisão é z = 0.
- Trocamos as variáveis e obtemos x = 5 e y = 0.
- Neste momento, y = 0 e o nosso algoritmo termina. O máximo divisor comum é o número x = 5.
O importante é que a ordem dos números não faz diferença. Se trocássemos os números do exemplo, obteríamos o par x = 35 e y = 50. O procedimento seria o mesmo:
- Dividimos x / y, isto é, dividimos 35 / 50, o que nos dá o resto z = 35.
- Trocamos as variáveis: x = 50 e y = 35.
- Vemos que, depois desse passo, apenas trocamos entre si o conteúdo das variáveis x e y…
Calculadora
Esta calculadora calcula o máximo divisor comum para você.
