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

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

בגרסה מורחבת מעט, מאפשר האלגוריתם האוקלידי לא רק למצוא את המחלק המשותף המקסימלי של שני מספרים, אלא גם להציג אותו כצירוף של מכפלות שלמות של שני המספרים, כלומר: אם <math>\ \gcd\left(a,b\right)=r</math> ניתן למצוא <math>m,n\isin\mathbb{Z}</math> כך ש <math>\ ma+nb=r</math>. האבחנה המרכזית בחישוב היא האבחנה הבאה: אם <math>\ a=qb+r</math>, וכבר ידועה לנו הצגה של <math>\ (b,r)</math> כצירוף לינאריליניארי <math>\ (b,r)=mb+nr</math>, ניתן לקבל משתי המשוואות את <math>\ (b,r)</math> כצירוף לינאריליניארי של <math>\ a,b</math> באמצעות הצבה פשוטה: <math>\ r=a-qb</math> ולכן <math>\ (a,b)=(b,r)=mb+nr=mb+n(a-qb)=na+(m-qn)b</math>.

להגדרה הכללית יש חיסרון אחד בולט: ברוב החוגים, ישנם זוגות של איברים שאין להם מחלק משותף מקסימלי. בעיה אחרת היא שהמחלק המשותף המקסימלי, אם קיים כזה, אינו יחיד; ההגדרה מבטיחה רק ששני מחלקים משותפים מקסימליים לאותם שני איברים, יחלקו זה את זה (איברים המחלקים זה את זה נקראים "ידידים"). מכיוון שאיברים ידידים יוצרים את אותו [[אידאל (אלגברה)|אידאלאידיאל]], אפשר לטפל בבעיה זו על ידי ניסוח ההגדרה בשפה של אידאליםאידיאלים:

* האידאלהאידיאל <math>\langle d\rangle</math> הוא מחלק משותף מקסימלי של a ו- b אם זהו האידאלהאידיאל הראשי המינימלי המכיל את האידאלהאידיאל <math>\langle a,b\rangle</math>.

מחלקה מיוחדת יותר של חוגים הם ה[[תחום ראשי|תחומים ראשיים]], המתאפיינים בכך שכל אידאלאידיאל הוא ראשי. בפרט, האידאלהאידיאל הנוצר על ידי זוג איברים הוא אידאלאידיאל ראשי, והיוצר שלו הוא המחלק המשותף המקסימלי.

[[פונקציה (תכנות)|פונקציה]] המממשת את האלגוריתם של אוקלידס בצורה רקורסיבית משמשת לעתיםלעיתים קרובות כדי להדגים את העוצמה של שימוש ב[[רקורסיה]] בתכנות. הפונקציה הבאה שמחשבת gcd מפתיעה בפשטותה, בזכות השימוש ברקורסיה. התחביר מתאים למספר שפות קרובות, ביניהן [[C (שפת תכנות)|C]] ו-[[Java]]. ניתן לכתוב פונקציה דומה בכל שפה שתומכת ברקורסיה.