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:
|
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.