Gli Elementi di Euclide
Libro VII

Proposizione 2

Dati due numeri che non siano primi fra loro, trovare il loro massimo comun divisore.

Svolgimento.  Siano AB, CD i due numeri dati che non sono primi fra loro. Si deve comunque trovare il massimo comun divisore di AB, CD.

Supponiamo dapprima che CD divida AB; ma esso, d’altra parte, divide anche sé medesimo per cui CD [in tal caso] è divisore comune di CD, AB. Ed è evidente che è anche il massimo; infatti nessun numero maggiore di CD può dividere CD.

Se invece CD non divide AB, ed a partire da AB, CD si continua a sottrarre di volta in volta il numero minore dal maggiore, la differenza dal minore, e così via, rimarrà un numero che dividerà  quello immediatamente precedente. Infatti non si avrà come ultimo resto l’unità; in caso contrario, AB, CD sarebbero primi fra loro, il che non è per ipotesi. Si avrà quindi un numero, come ultimo resto, che dividerà quello immediatamente precedente. E  allora CD, dividendo BE, lasci il resto EA minore di CD, mentre EA, dividendo DF, lasci il resto CF minore di EA, e si supponga che CF divida AE. Poiché dunque CF divide AE, ed AE divide DF, si ha che CF dividerà pure DF, ma divide anche se stesso, per cui dividerà anche tutta quanta la somma  CD. Ma CD divide BE; quindi anche CF divide BE; ma divide pure EA, per cui dividerà anche tutta quanta  la somma BA; ma esso divide pure CD, quindi CF è divisore comune di AB, CD. Dico ora che è anche il massimo. Infatti, se CF non fosse il massimo comun divisore di AB, CD, un altro numero, che fosse maggiore di CF, dividerebbe i numeri AB, CD. Li divida,  e sia esso G. E poiché G divide CD, ma CD divide BE, anche G divide BE; ma esso divide pure  tutta quanta la somma BA, per cui dividerà anche la differenza AE. Ma AE divide  DF; quindi anche G dividerà DF;  ma esso divide pure tutta quanta la somma  CD, per cui dividerà anche la differenza CF, cioè un numero maggiore dividerebbe un numero minore – il che è impossibile; non può quindi un altro numero, che sia maggiore di CF, dividere i numeri AB, CD; dunque CF è il massimo comun divisore di AB, CD.

In questo svolgimento Euclide rappresenta i numeri sotto forma di segmenti, come in figura:
Assumendo che sia AB maggiore di CD, si esegue prima la divisione  di AB per CD, che dà resto EA. Quindi si divide  CD per EA, ottenendo come resto FC.  Infine si divide EA per FC,  ed il resto questa volta è zero.  Si conclude che FC  è il massimo comune divisore di AB e CD: ciò viene dimostrato nella seconda parte dello svolgimento.

Quello proposto da Euclide  è l’algoritmo delle divisioni successive, che  col simbolismo moderno descriveremmo nel modo seguente.

Siano a, b due numeri interi positivi, supponiamo sia a>b. Sia q1 il quoziente e sia r1 il resto della divisione di a per b. Allora 0 £ r1 < b,  e si ha:
a = q1b + r1.

Se r1 = 0, allora b divide a, e quindi, come osserva Euclide,  b è il massimo comune divisore di a e b.  Altrimenti si procede eseguendo la divisione con resto di  b per r1 : detti q2   ed r2 il quoziente ed il resto si ha:
b = q2 r1 + r2,

 dove 0 £ r2 < r1.  Se r2  = 0,  allora r1 è il massimo comune divisore di a,b. Altrimenti l’algoritmo prosegue con:

r1 = q3 r2 + r3.

Poiché la successione dei resti è una successione di  numeri naturali strettamente decrescente, essa raggiungerà, prima o poi, lo zero.  L’algoritmo terminerà, cioè, ad un certo passo k-esimo,  quando si troverà come resto rk = 0 . Le ultime due righe saranno, quindi:

rk-3 = qk-1 rk-2 + rk-1
rk-2 = qk rk-1.

 
Il massimo comune divisore di a, b sarà l’ultimo resto diverso da zero, cioè rk-1.

Nello svolgimento di Euclide si esamina il caso particolare in cui l’algoritmo termina al terzo passo. All’epoca non esisteva un formalismo che permettesse di trattare il caso generale: ciò richiede, infatti, il ricorso  a variabili  dotate di indici, che compariranno solo in epoca moderna. Fino al 1500 era consuetudine dei matematici presentare le regole e procedimenti generali attraverso esempi concreti. D’altra parte questo tipo di esposizione non è affatto limitativo: esso ha, invece, indubbi vantaggi dal punto di vista della chiarezza, della semplicità e dell’efficacia didattica.  Quale insegnante, dovendo spiegare l’algoritmo euclideo ai suoi allievi, ne darebbe soltanto le formule senza svolgere  un esempio di calcolo?

Per di più, traducendo il testo di Euclide in linguaggio moderno, ci rendiamo conto che, pur disponendo di simboli astratti, non possiamo fare a meno di completare le formule con parole che ne descrivano il significato e l’utilizzo. Per avere un linguaggio totalmente simbolico è necessario compiere un passo in avanti nell’evoluzione  e ricorrere ad uno dei linguaggi di programmazione. Ecco l’algoritmo euclideo implementato in PASCAL:

PROGRAM  mcd(input, output)

      VAR a,b,r: integer;
   BEGIN
     readln (a, b);
     REPEAT
     r: = a MOD b;
     a: = b;
     b: = r;
     UNTIL r=0;
     write (a);
   END

Se confrontiamo questo con la versione di Euclide, vediamo che il salto è davvero notevole.  Certamente il  testo del programma è scritto in un codice artificiale praticamente incomprensibile ai non iniziati: esso è funzionale alla macchina,  ma decisamente ostico per l’uomo.  Un ottimo compromesso tra essenzialità  e chiarezza  è rappresentato dal diagramma di flusso, che riproduce le fasi della procedura di calcolo eseguita dal computer,  visualizzandone  la struttura logica in modo che essa venga colta d’un colpo solo. I complessi passaggi effettuati dai microcircuiti vengono tradotti in prescrizioni e domande,  la  sequenza delle operazioni è indicata da frecce.

Questo esempio è tratto dal testo scolastico Pascal e matematica di C. Di Comite e P. Ronchi (Scheda).

Gli Elementi di Euclide