מחלק משותף מקסימלי – הבדלי גרסאות

יעילות האלגוריתם זהה בסדר הגודל שלה ליעילות האלגוריתם הפשוט; מספר האיטרציות שמבצע האלגוריתם נותר זהה, ולכל איטרציה התווספו רק חישובים בסיסיים (מציאת q, חישוב m-qn).

 

 

בכל [[חוג (מבנה אלגברי)|חוג]] קומוטטיבי אפשר להגדיר מחלקים: איבר <math>a</math> מחלק איבר <math>b</math>, אם קיים איבר <math>t</math> כך ש-<math>b=ta</math>. יחס החילוק שהוגדר כאן הוא קדם-[[יחס סדר חלש|סדר חלש]] (הוא אינו אנטי-סימטרי), ובעזרתו אפשר לדבר על "מחלק מרבי" גם בחוגים שאין בהם יחס סדר טבעי: