Algoritmul lui Euclid consta in impartirea repetata a celui mai mare numar la cel mai mic numar si inlocuirea celui mai mare numar cu restul pana cand restul este egal cu zero. Apoi, ultimul numar diferit de zero obtinut este cel mai mare divizor comun intre cele doua numere initial date.