Le PGCD de deux nombres et le plus grand entier divisant chacun de ces deux nombres.
On peut l'obtenir par l'algorithme d'Euclide, en écrivant les divisions euclidiennes successives :
[tex]301=172 \times 1+129\\172=129 \times 1+43\\129=43 \times 3 +0[/tex]
Dès qu'on arrive à un reste égal à 0, on s'arrête. Le PGCD des deux nombres est le précédent reste. Ici, c'est 43.