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

 

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

 

ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על <math>\ \log_{\varphi}a</math> (כאן <math>\ \varphi</math> מסמן את [[יחס הזהב]]), כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המקסימלי של [[סדרת פיבונאצ'י|מספרי פיבונאצ'י]] עוקבים. מכאן שמציאת המחלק המשותף המקסימלי היא יעילה מבחינה חישובית; האלגוריתם פועל במהירות גם עבור מספרים גדולים, בני מאות ספרות.