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:


  1. 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\).
  2. 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