אלגוריתם אוקלידס – הבדלי גרסאות

האלגוריתם מבוסס על העיקרון הבא: לכל שלושה מספרים qa, b, c, מתקיים: <math>(qb+c,b) = (b,c)</math>. לכל זוג מספרים a,b {{כ}}(a גדול יותר), ניתן להציג את a כ-qb+c {{כ}}(c מינימלי) על ידי שימוש ב[[חילוק]] עם [[שארית (חילוק)|שארית]]. בצורה כזאת, הקטנו את אחד המספרים בלי לשנות את המחלק המשותף שלהם. אפשר להמשיך בתהליך שוב ושוב עד שמגיעים לזוג שאחד המספרים בו הוא 0; <math>(0,a)=a</math>, ולפיכך נמצא המחלק משותף הקטן ביותר.