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