Nechť splňují
Eukleidův algoritmus má na vstupu , jeho výstupem bude
Definujeme , posloupnost zbytků po dělení, a to rekurentně:
Tato posloupnost je klesající a existuje takové, že (protože nulou už nedělíme).
Označíme-li jako nejmenší takové, že , pak platí .
Tedy poslední nenulový člen je hledaným .
Je-li , rovnou platí .
Je-li (nějaké číslo je záporné) nebo neplatí-li (tedy nejsou seřazené), situaci převedeme na předchozí případ vztahem (tedy změním pořadí nebo dám absolutní hodnotu nebo oboje)