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

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

המחלק המשותף המקסימלי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המקסימלי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המקסימלי של 9 ו- 14 הוא 1, ואפשר להציג . תכונה זו מאפשרת לחשב הפכי מודולרי ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.

מקובל לסמן את המחלק המשותף המקסימלי של שני מספרים בסימון , או בקיצור .

שני מספרים שהמחלק המשותף המקסימלי שלהם הוא 1 (כדוגמת 9 ו- 14) נקראים מספרים זרים או "ראשוניים הדדית".

למחלק המשותף המקסימלי יש שימושים רבים בענפים אחרים של האלגברה המופשטת; בדומה למחלק המשותף המקסימלי של זוג מספרים שלמים, אפשר להגדיר מחלק משותף מקסימלי גם לזוג פולינומים או שלמים אלגבריים, ובאופן כללי ביותר, לזוג איברים בכל תחום שלמות.

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

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