2つの自然数、または整式の最大公約数を求める手法。

最古のアルゴリズムとして知られ、エウクレイデスの「原論」（紀元前300年頃）に記されている。

2つの自然数（または整式）a,b（a≧b）があるとき、bでaを割った余りを除数rとすると、
aとbの最大公約数と、bとrの最大公約数は等しいという性質がある。

この性質を利用して、rでbを割った除数、その除数でrを割った余り…と、
余りが0になるまで繰り返すと、その時の除数がaとbの最大公約数となる。