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

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

לחישוב <math>(a,b)</math> {{כ}}(כאשר a>b), אם b הוא 0, התוצאה היא a. אחרת, מצאמחלק את השארית c מהפרש a ב-b ומצא את השארית c; התוצאה היא <math>(b,c)</math> (שאותה יש לחשב בעזרת אותו אלגוריתם עצמו).