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

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