I Euklids originale version af algoritmen findes kvotienten og resten ved gentagen subtraktion; dvs. <math>r_{k-1}</math> trækkes fra <math>r_{k-2}</math>, indtil resten <math>r_k</math> er mindre end <math>r_{k-1}</math>. Derefter byttes der om på <math>r_k</math> og <math>r_{k-1}</math> (så <math>r_k</math> næste gang trækkes fra <math>r_{k-1}</math>), og processen gentages. Euklidisk opdeling reducerer alle trin mellem to opbytninger til et enkelt trin, hvilket er mere effektivt. Desuden er kvotienterne ikke nødvendige, så man kan erstatte division med rest med [[modulo]]operationen, der kun giver resten. Således bliver hver iteration af Euklids algoritme simpelthen
:<math>r_k=r_{k-2}\bmod r_{k-1}</math>
Religion Matematik