Este algoritmo pode ser implementado através de um dos códigos seguintes:
M é o máximo divisor comum |
Código da função MDC(a, b) |
|---|---|
|
u := a; v := b;
while u ≠ v do begin if u > v then u := u - v else v := v - u end M := u |
if a = b then M = a
else begin if a > b then M := MDC(a - b; b) else M := MDC(a; b - a) end |
Para provar que este algoritmo funciona, observamos os factos seguintes:
- Se d é um divisor comum dos inteiros positivos \(a\) e \(b\), com \(a\) > \(b\), então d é também um divisor comum dos inteiros positivos \(b\) e \(a\) - \(b\).
- O algoritmo produz sucessivamente inteiros positivos cada vez mais pequenos, e, portanto, termina com um numero inteiro ≥ 1.
O algoritmo de Euclides, tal como ele o enunciou nos Elementos, pode não ser muito eficiente. Por exemplo, se tentarmos encontrar MDC(101, 10100 + 1) por subtração repetida, teremos que subtrair 101 de 10100 + 1 quase 1098 vezes, o que não é, evidentemente, muito rápido.
No entanto, subtrair repetidamente \(b\) de \(a\), até que a diferença, \(r\) = \(a\) - \(b\), seja menor do que \(b\), é o mesmo que dividir (\(a\) por \(b\) e obter o resto \(r\), como se ilustra na figura seguinte.
Isto dá origem ao seguinte algoritmo de divisão Euclideana: Dados dois números naturais \(a\) e \(b\), com \(a\) > \(b\) e \(b\) ≠ 0, existem números naturais \(q\) e \(r\), “quociente” e “resto”, tais que:
\(a = qb + r\) onde \(0 ≤ r < b\)
A propriedade de divisão é visualmente óbvia, como se ilustra na figura acima, porque qualquer número natural a deve estar entre múltiplos sucessivos de \(b\) - na figura, entre \(qb\) e (\(q + 1\))b. Em particular, a sua distância \(r\), ao múltiplo menor, \(qb\), e menor do que a distância \(b\) entre eles.
A vantagem do algoritmo de divisão euclideana, é que, em geral, é muito mais rápido do que a subtração repetida. Cada divisão de um número natural \(b\) por um número \(a < b\), com \(k\) algarismos, “cancela” cerca de \(k\) algarismos em \(b\), e conduz a um resto \(r\) com no máximo \(k\) algarismos. Portanto, o número de divisões e no máximo igual ao número total de dígitos dos números com que começámos. Resumindo
MDC(\(a, b\)) = MDC(\(b, r\)), onde \(a = qb + r\)
Por exemplo
MDC(1345, 24) = MDC(24, 1) = 1
já que 1345 = 24 × 56 + 1. Em geral, podemos calcular M = MDC(\(a\), \(b\)) através do código seguinte:
|
u := a; v := b;
while v > 0 do begin r := u mod v; u := v; v := r; end M := u |
Recursos relacionados disponíveis na Casa das Ciências:
Criada em 20 de Setembro de 2018
Revista em 22 de Setembro de 2018
Aceite pelo editor em 4 de Outubro de 2018
