מחלק משותף מקסימלי

בתורת המספרים, מחלק משותף מקסימלי  (או מחלק משותף גדול ביותר, ממג"ב; וכן gcd קיצור של greatest common divisor) של שני מספרים שלמים הוא המספר הגדול ביותר שמחלק את שניהם. למשל, המחלק המשותף המקסימלי של 12 ו־18 הוא 6. במושג זה, שהוא אבן פינה בתורת המספרים האלמנטרית, עסק כבר אוקלידס, שאף כלל בספרו, יסודות, אלגוריתם לחישוב המחלק המשותף המקסימלי.
המחלק המשותף המקסימלי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המקסימלי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המקסימלי של 9 ו- 14 הוא 1, ואפשר להציג . תכונה זו מאפשרת לחשב הפכי מודולרי ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.
מקובל לסמן את המחלק המשותף המקסימלי של שני מספרים  בסימון , או בקיצור .
שני מספרים שהמחלק המשותף המקסימלי שלהם הוא 1 (כדוגמת 9 ו- 14) נקראים מספרים זרים או "ראשוניים הדדית".
למחלק המשותף המקסימלי יש שימושים רבים בענפים אחרים של האלגברה המופשטת; בדומה למחלק המשותף המקסימלי של זוג מספרים שלמים, אפשר להגדיר מחלק משותף מקסימלי גם לזוג פולינומים או שלמים אלגבריים, ובאופן כללי ביותר, לזוג איברים בכל תחום שלמות.

כמה תכונות של המחלק המשותף המקסימלי

המחלק המשותף המקסימלי של a ו- b מוגדר היטב, פרט למקרה ש-  (אז כל מספר מחלק את שניהם). מקרים מיוחדים אחרים הם: ; ; . תכונה חשובה נוספת, העומדת בבסיס ההגדרה של חבורת אוילר: אם a,b זרים, אז לכל n, . כמו כן, הוא מחלק כל צירוף ליניארי במקדמים שלמים של a ו-b (ולכן בפרט הוא המספר החיובי הקטן ביותר שניתן לקבל כצירוף ליניארי במקדמים שלמים שלהם).

חישוב המחלק המשותף המקסימלי

את המחלק המשותף המקסימלי של שני מספרים אפשר לחשב בנקל מתוך הפירוק לגורמים שלהם; כך לדוגמה המחלק המשותף המקסימלי של 495 ו-525 הוא 15, לפי החישוב:
.
עם זאת, מציאת הפירוק לגורמים היא בעיה קשה, והרבה יותר קל מבחינה חישובית למצוא את המחלק המשותף המקסימלי ישירות, ללא חישוב הגורמים הראשוניים.
האלגוריתם של אוקלידס לחישוב המחלק המשותף המקסימלי הוא האלגוריתם הקדום ביותר שהופיע בכתב, אף על פי שללא ספק היו כבר לבבלים שיטות לביצוע חישובים מסוגים שונים. ראשוניותו בכך שהוא עוסק במפורש במקרה הכללי, ואיננו נדרשים להסיק על הצעדים שהוא מפעיל מתוך דוגמאות בודדות.
האלגוריתם מבוסס על אבחנה יסודית: לכל b,q,r, המחלקים המשותפים של b ושל r הם גם המחלקים המשותפים ל- b ול- bq+r. לפיכך, לשני הזוגות יש אותו מחלק משותף מקסימלי: . 
כדי לחשב את המחלק המשותף המקסימלי של שני מספרים טבעיים a,b, פעל באופן הבא: חלק את המספר הגדול (נאמר, a), במספר הקטן, וכתוב a=qb+r, כאשר  היא השארית. אם r=0, אז המחלק המשותף המקסימלי שווה ל- b. אחרת, המחלק המשותף המקסימלי שווה לזה של b ושל r (ומכיוון שהמספר הגדול בזוג זה קטן מן המספר הגדול בזוג הקודם, התהליך מתקדם ומגיע בהכרח אל סופו).
ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על  (כאן  מסמן את יחס הזהב), כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המקסימלי של מספרי פיבונאצ'י עוקבים. מכאן שמציאת המחלק המשותף המקסימלי היא יעילה מבחינה חישובית; האלגוריתם פועל במהירות גם עבור מספרים גדולים, בני מאות ספרות.

הצגת המחלק המשותף המקסימלי כצירוף שלם של גורמיו

בגרסה מורחבת מעט, מאפשר האלגוריתם האוקלידי לא רק למצוא את המחלק המשותף המקסימלי של שני מספרים, אלא גם להציג אותו כצירוף של מכפלות שלמות של שני המספרים, כלומר: אם  ניתן למצוא  כך ש . האבחנה המרכזית בחישוב היא האבחנה הבאה: אם , וכבר ידועה לנו הצגה של  כצירוף ליניארי , ניתן לקבל משתי המשוואות את  כצירוף ליניארי של  באמצעות הצבה פשוטה:  ולכן .
ניתן לסכם את האמור לעיל באלגוריתם הבא:
Extended_GCD(a,b)
1. if b == 0 return [a,1,0]
2. q = a/b, r = a%b
3. [d,m,n]=Extended_GCD(b,r)
4. return [d,n,m-qn]
יעילות האלגוריתם זהה בסדר הגודל שלה ליעילות האלגוריתם הפשוט; מספר האיטרציות שמבצע האלגוריתם נותר זהה, ולכל איטרציה התווספו רק חישובים בסיסיים (מציאת q, חישוב m-qn).

כלי להדגמת רקורסיה

פונקציה המממשת את האלגוריתם של אוקלידס בצורה רקורסיבית משמשת לעיתים קרובות כדי להדגים את העוצמה של שימוש ברקורסיה בתכנות. הפונקציה הבאה שמחשבת gcd מפתיעה בפשטותה, בזכות השימוש ברקורסיה. התחביר מתאים למספר שפות קרובות, ביניהן C ו-Java. ניתן לכתוב פונקציה דומה בכל שפה שתומכת ברקורסיה.
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);}