|
ב[[תורת המספרים]], '''מחלק משותף מקסימלימרבי''' (או '''מחלק משותף גדול ביותר''', '''ממג"ב'''; וכן '''gcd''' קיצור של '''greatest common divisor''') של שני [[מספר שלם|מספרים שלמים]] הוא המספר הגדול ביותר ש[[חילוק|מחלק]] את שניהם. למשל, המחלק המשותף המקסימליהמרבי של 12 ו־18 הוא 6. במושג זה, שהוא [[אבן פינה]] בתורת המספרים האלמנטרית, עסק כבר [[אוקלידס]], שאף כלל בספרו, [[יסודות (ספר)|יסודות]], [[אלגוריתם]] ל[[חישוב]] המחלק המשותף המקסימליהמרבי.
המחלק המשותף המקסימליהמרבי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המקסימליהמרבי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המקסימליהמרבי של 9 ו- 14 הוא 1, ואפשר להציג <math>\ 1 = 2\cdot 14 - 3 \cdot 9</math>. תכונה זו מאפשרת לחשב הפכי [[חשבון מודולרי|מודולרי]] ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.
מקובל לסמן את המחלק המשותף המקסימליהמרבי של שני מספרים <math>\ a, b</math> בסימון <math>\gcd\left(a,b\right)</math>, או בקיצור <math>\ (a,b)</math>.
שני מספרים שהמחלק המשותף המקסימליהמרבי שלהם הוא 1 (כדוגמת 9 ו- 14) נקראים [[מספרים זרים]] או "ראשוניים הדדית".
למחלק המשותף המקסימליהמרבי יש שימושים רבים בענפים אחרים של ה[[אלגברה מופשטת|אלגברה המופשטת]]; בדומה למחלק המשותף המקסימליהמרבי של זוג מספרים שלמים, אפשר להגדיר מחלק משותף מקסימליהמרבי גם לזוג [[פולינום|פולינומים]] או [[חוג השלמים האלגבריים|שלמים אלגבריים]], ובאופן כללי ביותר, לזוג איברים בכל [[תחום שלמות]].
== כמה תכונות של המחלק המשותף המקסימלי ==
| 