Un algoritmo para calcular el máximo común divisor ... ( Artículo escrito en catalán )

    En un altre article exposava l'algorisme de les diferències successives per trobar el màxim comú divisor de dos nombres naturals, un algorisme molt natural i ben conegut pels antics matemàtics grecs. Ara, n'exposaré un altre de molt eficaç per trobar també el màxim comú divisor de dos nombres naturals: l'algorisme dit d'Euclides. Aquest algorisme està emparentat amb l'anterior pel fet que també es fonamenta en la idea de fer ús d'una quantia patró (el màxim comú divisor) amb la qual cobrir exactament dues magnituds (els dos nombres donats), però fent ús, ara, del teorema de la divisió euclidiana per controlar el valor del residu de les divisions, quantitat que, quan és nul·la, ens indica l'assoliment de la mesura patró, que serà el valor del divisor en el pas que toqui. A sota, escric aquest algorisme d'una forma més acurada:

procediment mcd_euclides(a,b);
comença
  defineix D:enter; // variable auxiliar que representa el dividend
  defineix d:enter; // variable auxiliar que representa el divisor
  defineix r:enter; // variable auxiliar que representa el residu 
  si a < b
    {
     { 
       D:=a;
       d:=b; 
     }
    altrament
     {
       D:=b;
       d:=a; 
     }
    }
    fes
        {
          r:=residu(D div d);
          si r < 0  llavors 
             {
               D:=d;
               d:=r;
             }
        }
    mentre r > 0
  escriu "mcd(a,b)=",d;
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:
    $D \leftarrow 15$ i $d \leftarrow 12$    
i obtenim
    $r=3$ ( el valor del residu de la divisió )
i com que r > 0, continuem
------------------------
pas número 2:
    $D \leftarrow 12$ i $d \leftarrow 3$     ( assignem al nou dividend l'antic divisor i al nou divisor l'antic residu )
i obtenim
    $r=0$ ( el valor del residu de la divisió )
i, per tant, concloem que mcd(15,12)=3     (ja que aquest és el valor de $d$ en el pas que $r=0$ ), 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]