Por kalkuli la pgkd de du nombroj, oni povas uzi metodon nomatan algoritmo de Eŭklido (oni ne pruvos ĉi tie la validecon de tiu algoritmo). Jen la principo:
Donitaj du pozitivalaj entjeroj a kaj b, oni komence provu ĉu b estas nul. Se jes, tiam la PGKD egalas a. Se ne, oni kalkulu r, la resto de la divido de a per b. Anstataŭigu a per b, poste b per r, kaj rekomencu la procedon.
Ni kalkulu, ekzemple, la pgkd de 2160 kaj 888 per tiu algoritmo; jen la stadioj:
a | b | r |
2160 | 888 | 384 |
888 | 384 | 120 |
384 | 120 | 24 |
120 | 24 | 0 |
24 | 0 | |
La pgkd de 2160 kaj 888 estas do 24. Estas neniu pli granda entjero kiu dividas tiujn du nombrojn. (Efektive 2160 = 24 × 90 kaj 888 = 24 × 37).
La pgkd estas efektive la lasta ne nula resto.