Az euklideszi algoritmus

Definíció

Olyan véges sokszor elvégzett maradékos osztás, amely megadja két természetes szám legnagyobb közös osztóját.

Az eljárás folyamán az egyik számot elosztjuk maradékosan a másik számmal, majd a másodikat a maradékkal, az első maradékot az második maradékkal, és így tovább. Az utolsó nem nulla maradék a legnagyobb közös osztó.