Cálculo del máximo común divisor mediante el algoritmo de las diferencias. ( Artículo escrito en catalán )

    Una manera molt natural de calcular el màxim comú divisor de dos nombres naturals a i b consisteix a prendre al més petit de tots dos com a quantia patró i mirar si comprèn exactament al més gran; si això és així, el màxim comú divisor és igual al més petit de tots dos i, en cas contrari, cal iterar aquest operació de resta, canviant el minuend pel resultat i mantenint el subtrahend si aquesta diferència dóna un nombre més gran que aquest (altrament, cal intercanviar el minuend pel subtrahend). Això es repeteix fins obtenir una diferència igual a zero. Llavors, lògicament, el màxim comú divisor de tots dos nombres ( a i b ) és igual al valor del minuend (que és igual al nou subtrahend). Escriurem aquest algorisme d'una forma més polida:

procediment mcd_diferencies(a,b);
comença
  defineix m:enter; // variable auxiliar
    fes
        {
          si a < b llavors 
             {m:=a, a:=b; b:=m}
          a:=a-b;
        }
    mentre |a-b|> 0
  escriu "mcd(a,b)=",a;
acaba.

Exemple:
    Calculeum el màxim comú divisor dels nombres naturals 15 i 12 fent ús de l'algorisme de les diferències:
------------------------
pas número 1:
    $a=15$ i $b=12$     (a és més gran que b )
per tant fem
    $a \leftarrow 15-12$     (a=3, b=12)
i com que |a-b| > 0, continuem
------------------------
pas número 2:
    $a=3$ i $b=12$     ( a és més petit que b )
per tant fem
    $m \leftarrow 3$, $a \leftarrow 12$, $b \leftarrow 3$
    $a \leftarrow 12-3$     (a=9, b=12)
i com que |a-b| > 0, continuem
------------------------
pas número 3:
    $a=9$ i $b=12$     ( a és més petit que b)
per tant fem
    $m \leftarrow 9$, $a \leftarrow 12$, $b \leftarrow 9$
    $a \leftarrow 12-9$     (a=3, b=9)
i com que |a-b| > 0, continuem
------------------------
pas número 4:
    $a=3$ i $b=9$     ( a és més petit que b)
per tant fem
    $m \leftarrow 3$, $a \leftarrow 9$, $b \leftarrow 3$
    $a \leftarrow 9-3$     (a=6, b=3)
i com que |a-b| > 0, continuem
------------------------
pas número 5:
    $a=6$ i $b=3$     ( a és més gran que b)
per tant fem
    $a \leftarrow 6-3$     (a=3, b=3)
i com que |a-b| = 0, concloem que mcd(15,12) = 3 i acabem.
$\square$

Observació:     Aquí s'ha implementat l'algorisme a mà perquè els nombres de l'exemple són petits. Si els nombres fossin més grans convindria fer ús d'algun llenguatge de programació per poder implementar de manera automàtica l'algorisme en un ordinador o en una calculadora programable. Suggereixo MAXIMA.

[nota del autor]