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

המחלק המשותף המקסימלי של מספרים, המסומן {{משמאל לימין|<math>gcd(a,b)}}</math> או בקיצור (a,b), היא פעולה המקבלת שני מספרים טבעיים, ומחזירה את המספר הגדול ביותר ש[[מחלק]] את שניהם.

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

ניתן לחשב את m,n בעזרת אלגוריתם אוקלידס בעזרת התכונה שאם כל פעם השתמשנו ב-<math>a=c+qb</math>, אז <math>c=a-qb</math>. לפיכך, אם אנחנו יודעים בשלב מסוים איך להציג את שני המספרים <math>a</math> ו-<math>b</math> בצורה <math>mA+nB</math> (ההתחלה פשוטה: <math>n=0</math> ,<math>m=1</math>,n=0 או להפך) ניתן להציב בביטוי <math>c=a-qb</math> ולהתקדם בשלבי האלגוריתם עד להצגה הרצויה.

לדוגמה, נמצא בדוגמה לעיל את ההצגה של 10 כ-<math>100n+230m</math>:

לפיכך: <math>n=7, m=-3</math>.