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

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

המחלק המשותף המרבי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המרבי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המרבי של 9 ו-14 הוא 1, ואפשר להציג ${\displaystyle 1=2\cdot 14-3\cdot 9}$. תכונה זו מאפשרת לחשב הפכי מודולרי ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.

מקובל לסמן את המחלק המשותף המרבי של שני מספרים ${\displaystyle a,b}$ בסימון ${\displaystyle \gcd \left(a,b\right)}$, או בקיצור ${\displaystyle (a,b)}$.

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

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

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

המחלק המשותף המרבי של ${\displaystyle a}$ ו-${\displaystyle b}$ מוגדר היטב, פרט למקרה ש-${\displaystyle a=b=0}$ (אז כל מספר מחלק את שניהם). מקרים מיוחדים אחרים הם: ${\displaystyle (a,0)=a}$; ${\displaystyle (a,a)=a}$; ${\displaystyle (a,1)=1}$. תכונה חשובה נוספת, העומדת בבסיס ההגדרה של חבורת אוילר: אם ${\displaystyle a,b}$ זרים, אז לכל ${\displaystyle n}$, ${\displaystyle (n,ab)=(n,a)(n,b)}$. כמו כן, הוא מחלק כל צירוף ליניארי במקדמים שלמים של ${\displaystyle a}$ ו-${\displaystyle b}$ (ולכן בפרט הוא המספר החיובי הקטן ביותר שניתן לקבל כצירוף ליניארי במקדמים שלמים שלהם).

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

את המחלק המשותף המרבי של שני מספרים אפשר לחשב בנקל מתוך הפירוק לגורמים שלהם; כך לדוגמה המחלק המשותף המרבי של 495 ו-525 הוא 15, לפי החישוב:

${\displaystyle {\mbox{gcd}}(495,525)={\mbox{gcd}}(3^{2}\cdot 5\cdot 11,3\cdot 5^{2}\cdot 7)=3\cdot 5=15}$.

עם זאת, מציאת הפירוק לגורמים היא בעיה קשה, והרבה יותר קל מבחינה חישובית למצוא את המחלק המשותף המרבי ישירות, ללא חישוב הגורמים הראשוניים.

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

האלגוריתם מבוסס על אבחנה יסודית: לכל ${\displaystyle b,q,r}$, המחלקים המשותפים של ${\displaystyle b}$ ושל ${\displaystyle r}$ הם גם המחלקים המשותפים ל-${\displaystyle b}$ ול-${\displaystyle bq+r}$. לפיכך, לשני הזוגות יש אותו מחלק משותף מרבי: ${\displaystyle (qb+r,b)=(b,r)}$. כדי לחשב את המחלק המשותף המרבי של שני מספרים טבעיים ${\displaystyle a,b}$ פעל באופן הבא: חלק את המספר הגדול (נאמר, ${\displaystyle a}$), במספר הקטן, וכתוב ${\displaystyle a=qb+r}$, כאשר ${\displaystyle 0\leq r<b}$ היא השארית. אם ${\displaystyle r=0}$, אז המחלק המשותף המרבי שווה ל-${\displaystyle b}$. אחרת, המחלק המשותף המרבי שווה לזה של ${\displaystyle b}$ ושל ${\displaystyle r}$ (ומכיוון שהמספר הגדול בזוג זה קטן מן המספר הגדול בזוג הקודם, התהליך מתקדם ומגיע בהכרח אל סופו).

ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על ${\displaystyle \log _{\varphi }a}$ (כאן ${\displaystyle \varphi }$ מסמן את יחס הזהב), כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המרבי של מספרי פיבונאצ'י עוקבים. מכאן שמציאת המחלק המשותף המרבי היא יעילה מבחינה חישובית; האלגוריתם פועל במהירות גם עבור מספרים גדולים, בני מאות ספרות.

דוגמה

המחלק המשותף המרבי של 1071 ו־1029 הוא 21. נראה זאת באמצעות האלגוריתם האוקלידי:

a	b	q	r
1071	1029	1	42
1029	42	24	21
42	21	2	0
21	0

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

בגרסה מורחבת מעט, מאפשר האלגוריתם האוקלידי לא רק למצוא את המחלק המשותף המרבי של שני מספרים, אלא גם להציג אותו כצירוף של מכפלות שלמות של שני המספרים, כלומר: אם ${\displaystyle \gcd \left(a,b\right)=r}$ ניתן למצוא ${\displaystyle m,n\in \mathbb {Z} }$ כך ש ${\displaystyle ma+nb=r}$. האבחנה המרכזית בחישוב היא האבחנה הבאה: אם ${\displaystyle a=qb+r}$, וכבר ידועה לנו הצגה של ${\displaystyle (b,r)}$ כצירוף ליניארי ${\displaystyle (b,r)=mb+nr}$, ניתן לקבל משתי המשוואות את ${\displaystyle (b,r)}$ כצירוף ליניארי של ${\displaystyle a,b}$ באמצעות הצבה פשוטה: ${\displaystyle r=a-qb}$ ולכן ${\displaystyle (a,b)=(b,r)=mb+nr=mb+n(a-qb)=na+(m-qn)b}$.

ניתן לסכם את האמור לעיל באלגוריתם הבא:

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).

מחלק משותף מרבי בתחומי שלמות

בכל חוג קומוטטיבי אפשר להגדיר מחלקים: איבר ${\displaystyle a}$ מחלק איבר ${\displaystyle b}$, אם קיים איבר ${\displaystyle t}$ כך ש-${\displaystyle b=ta}$. יחס החילוק שהוגדר כאן הוא קדם-סדר חלש (הוא אינו אנטי-סימטרי), ובעזרתו אפשר לדבר על "מחלק מרבי" גם בחוגים שאין בהם יחס סדר טבעי:

• איבר ${\displaystyle d}$ הוא מחלק משותף מרבי של איברים ${\displaystyle a,b}$, אם ${\displaystyle d}$ מחלק את ${\displaystyle a}$ ואת ${\displaystyle b}$, וכל איבר המחלק את שניהם, מחלק את ${\displaystyle d}$.

הגדרה זו מתלכדת עם ההגדרה הרגילה, המתאימה רק לחוג השלמים.

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

• האידיאל ${\displaystyle \langle d\rangle }$ הוא מחלק משותף מרבי של ${\displaystyle a}$ ו-${\displaystyle b}$ אם זהו האידיאל הראשי המזערי המכיל את האידיאל ${\displaystyle \langle a,b\rangle }$.

ישנם תחומי שלמות מיוחדים, שבהם תמיד קיים מחלק משותף מרבי. אחת הדוגמאות היא תחום פריקות יחידה: בחוג כזה, אפשר לכתוב כל זוג איברים ${\displaystyle a}$ ו-${\displaystyle b}$ כמכפלות ${\displaystyle a=up_{1}^{t_{1}}\dots p_{n}^{t_{n}}}$ ו-${\displaystyle b=vp_{1}^{s_{1}}\dots p_{n}^{s_{n}}}$, כאשר ${\displaystyle u,v}$ הפיכים ו-${\displaystyle p_{1},\dots ,p_{n}}$ הם ראשוניים של החוג, שאינם ידידים זה לזה. במקרה זה, המחלק המשותף המרבי הוא ${\displaystyle p_{1}^{\min(t_{1},s_{1})}\dots p_{n}^{\min(t_{n},s_{n})}}$.

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

בין התחומים הראשיים, החוגים האוקלידיים מתאפיינים בכך שאפשר לבצע בהם חילוק עם שארית. אלו הם בדיוק החוגים שבהם אפשר לממש את האלגוריתם של אוקלידס שתואר לעיל.

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

פונקציה המממשת את האלגוריתם של אוקלידס בצורה רקורסיבית משמשת לעיתים קרובות כדי להדגים את העוצמה של שימוש ברקורסיה בתכנות. הפונקציה הבאה שמחשבת gcd מפתיעה בפשטותה, בזכות השימוש ברקורסיה. התחביר מתאים למספר שפות קרובות, ביניהן C ו-Java. ניתן לכתוב פונקציה דומה בכל שפה שתומכת ברקורסיה.

int gcd(int a, int b) {
    if (b==0) return (a);
    else return gcd(b, a % b);
}

ראו גם

• כפולה משותפת מינימלית

קישורים חיצוניים

מדיה וקבצים בנושא מחלק משותף מקסימלי בוויקישיתוף

• מחשב מחלק משותף מקסימלי
• מחלק משותף מקסימלי, באתר MathWorld (באנגלית)