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

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

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

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

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

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

Other Languages
azərbaycanca: ƏBOB
Bahasa Indonesia: Faktor persekutuan terbesar
日本語: 最大公約数
한국어: 최대공약수
srpskohrvatski / српскохрватски: Najveći zajednički djelitelj brojeva
Simple English: Greatest common divisor
తెలుగు: గ.సా.భా
Türkçe: Ortak bölen
татарча/tatarça: Иң зур уртак бүлүче
اردو: عاد اعظم