ALGORITMO DI EUCLIDE

L'algoritmo di Euclide è scandito nei seguenti passi: 

1.  si inizia con la divisione fra i 2 numeri di cui si intenda determinare il MCD, avendo l'accortezza di considerare come dividendo il maggiore dei 2 e divisore l'altro;

2. quindi si opera una nuova divisione fra i termini che in quella precedente erano rispettivamente il quoziente e il resto;

3. si itera il procedimento, fino a quando non si ottenga come resto 0;

4. si considera l'ultimo resto non nullo (cioè diverso da 0): questo è il MCD cercato.

Esempio: 

calcolare il MCD(28;20) con l'algoritmo di Euclide.

Applichiamo l'algoritmo, come appena descritto:

Il principio di base su cui si fonda sul fatto che MCD(a;b) = MCD(b; r = resto della divisione fra a e b). Infatti, ogni numero che divide sia a sia b deve dividere anche r. Di conseguenza, l'insieme dei divisori comuni di A e B è lo stesso di B e R, quindi il loro Massimo Comune Divisore (MCD) è identico. 

Questo induce il passo succesivo dell'algoritmo, per il quale vale lo stesso principio.

Nell'esempio: MCD(28;20) = MCD(20;8) = MCD(8;4) = 4

Questo algoritmo permette di determinare il MCD fra 2  numeri senza ricorrere alla fattorizzazione che sappiamo bene essere tanto più impegnativa quanto più si considerino numeri grandi: questo è il suo vantaggio.

L'algoritmo di Euclide può essere utilizzato anche per ridurre ai minimi termini una frazione.