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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

שני מספרים שהמחלק המשותף המקסימלי שלהם הוא 1 (כדוגמת 9 ו- 14) נקראים מספרים זרים או "ראשוניים הדדית". מקובל לסמן את המחלק המשותף המקסימלי של שני מספרים $\ a, b$ בסימון $\gcd\left(a,b\right)$ , או בקיצור $\ (a,b)$ .

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

תוכן עניינים

1 כמה תכונות של המחלק המשותף המקסימלי
2 חישוב המחלק המשותף המקסימלי
- 2.1 דוגמה
- 2.2 הצגת המחלק המשותף המקסימלי כצירוף שלם של גורמיו
3 מחלק משותף מקסימלי בחוגים כלליים
4 ראו גם
5 קישורים חיצוניים

[עריכה] כמה תכונות של המחלק המשותף המקסימלי

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

[עריכה] חישוב המחלק המשותף המקסימלי

את המחלק המשותף המקסימלי של שני מספרים אפשר לחשב בנקל מתוך הפירוק לגורמים שלהם; למשל, $\ \mbox{gcd}(3^2\cdot 5\cdot 11,3\cdot 5^2\cdot 7)=3\cdot 5=15$ . עם זאת, מציאת הפירוק לגורמים היא בעיה קשה, והרבה יותר קל מבחינה חישובית למצוא את המחלק המשותף המקסימלי ישירות, ללא חישוב הגורמים הראשוניים.

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

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

ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על $\ \log_{\frac{1+\sqrt{5}}{2}}a$ , כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המקסימלי של מספרי פיבונאצ'י עוקבים.

[עריכה] דוגמה

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

a	b	r
1071	1029	42
1029	42	21
42	21	0
21	0

[עריכה] הצגת המחלק המשותף המקסימלי כצירוף שלם של גורמיו

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

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

התקיים:

$\ (1029,42)=(42,21)=21$

כיוון ש:

$\ 1029 = 24\cdot 42 + 21$

כלומר:

$\ 21 = 1029-24\cdot 42$ (א)

כמו כן:

$\ (1071,1029)=(1029,42)$

כיוון ש:

$\ 1071 = 1\cdot 1029 + 42$

כלומר:

$\ 42=1071-1\cdot 1029$ (ב)

עתה, אם נציב את ב' בא', נקבל:

$\ 21 = 1029-24\cdot 1071 + 24\cdot 1029 = 25\cdot 1029-24\cdot 1071$

ומצאנו דרך להציג את $\ 21$ כצירוף לינארי של $\ 1071,1029$ , כרצוי.

[עריכה] מחלק משותף מקסימלי בחוגים כלליים

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

איבר d הוא מחלק משותף מקסימלי של איברים a,b, אם d מחלק את a ואת b, וכל איבר המחלק את שניהם, מחלק את d.

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

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

האידאל $\ <d>$ הוא מחלק משותף מקסימלי של a ו- b אם זהו האידאל הראשי המינימלי המכיל את האידאל $\ <a,b>$ .

ישנם תחומי שלמות מיוחדים, שבהם תמיד קיים מחלק משותף מקסימלי. הדוגמה הכללית ביותר היא תחום פריקות יחידה: בחוג כזה, אפשר לכתוב כל זוג איברים a ו- b כמכפלות $\ a=u p_1^{t_1}\dots p_n^{t_n}$ ו- $\ b=u p_1^{s_1}\dots p_n^{s_n}$ , כאשר u,v הפיכים ו- $\ p_1,\dots,p_n$ הם ראשוניים של החוג, שאינם ידידים זה לזה. במקרה זה, המחלק המשותף המקסימלי הוא $\ p_1^{\min(t_1,s_1)}\dots p_n^{\min(t_n,s_n)}$ .

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

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