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

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

בתכונה זו ניתן להשתמש בכיוון ההפוך - במקום להגדיל את אחד המספרים, מקטינים אותו: לכל זוג מספרים 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. אחרת, חלק את a ב-b ומצא את השארית c; התוצאה היא <math>*(b,c)</math> (שאותה יש לחשב בעזרת אותו אלגוריתם עצמו).

ראשית יש [[הוכחה|להוכיח]] את השוויון <math>*(b,c+qb) = *(b,c)</math>.

קיבלנו שמספר הוא מחלק משותף של <math>c+qb</math> ושל b [[אם ורק אם]] הוא מחלק משותף של b ושל c. לכן [[קבוצה (מתמטיקה)|קבוצת]] המחלקים המשותפים של הזוגות זהה, ובפרט האיבר המקסימלי שלהם זהה. מכאן <math>*(b,c+qb) = *(b,c)</math>.