Euklideszi algoritmus

Számok legnagyobb közös osztójának meghatározása az euklideszi algoritmus segítségével.

Számok legnagyobb közös osztójának alábbi algoritmusát Eukleidész határozta meg.

Ez az algoritmus az alábbi oszthatósággal kapcsolatos észrevételen alapszik: Ha a=b⋅q+r, akkor (a,b)=(b,r), ahol a, b, q, r egész számok. Mivel a maradékos osztás maradéka mindig kisebb az osztónál, ezért két szám legnagyobb közös osztójának meghatározása mindig visszavezethető két kisebb szám legnagyobb közös osztójának megkeresésére.

Például: Határozzuk meg 252 és 2205 legnagyobb közös osztóját. 

2205=252⋅8+189, és (2205,252)=(252,189)
252=189⋅1+63, és (252,189)=(189,63)
189=63⋅3+0, és (189,63)=63

 Vagyis (252,2205)=63.