מחלק משותף מקסימלי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט החלפות: אידיאל, לעיתים, \1ליניארי |
מ replaced: למרות ש ← אף על פי ש באמצעות AWB |
||
שורה 1:
ב[[תורת המספרים]], '''מחלק משותף מקסימלי''' (או '''מחלק משותף גדול ביותר''', '''ממג"ב'''; וכן '''gcd''' קיצור של '''greatest common divisor''') של שני [[מספר שלם|מספרים שלמים]] הוא המספר הגדול ביותר ש[[חילוק|מחלק]] את שניהם. למשל, המחלק המשותף המקסימלי של 12 ו־18 הוא 6. במושג זה, שהוא [[אבן פינה]] בתורת המספרים האלמנטרית, עסק כבר [[אוקלידס]], שאף כלל בספרו, [[יסודות (ספר)|יסודות]], [[אלגוריתם]] ל[[חישוב]] המחלק המשותף המקסימלי.
המחלק המשותף המקסימלי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המקסימלי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המקסימלי של 9 ו- 14 הוא 1, ואפשר להציג <math>\ 1 = 2\cdot 14 - 3 \cdot 9</math>. תכונה זו מאפשרת לחשב הפכי [[חשבון מודולרי|מודולרי]] ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.
שורה 5:
מקובל לסמן את המחלק המשותף המקסימלי של שני מספרים <math>\ a, b</math> בסימון <math>\gcd\left(a,b\right)</math>, או בקיצור <math>\ (a,b)</math>.
שני מספרים שהמחלק המשותף המקסימלי שלהם הוא 1 (כדוגמת 9 ו- 14) נקראים [[מספרים זרים]] או "ראשוניים הדדית".
למחלק המשותף המקסימלי יש שימושים רבים בענפים אחרים של ה[[אלגברה מופשטת|אלגברה המופשטת]]; בדומה למחלק המשותף המקסימלי של זוג מספרים שלמים, אפשר להגדיר מחלק משותף מקסימלי גם לזוג [[פולינום|פולינומים]] או [[חוג השלמים האלגבריים|שלמים אלגבריים]], ובאופן כללי ביותר, לזוג איברים בכל [[תחום שלמות]].
== כמה תכונות של המחלק המשותף המקסימלי ==
שורה 17:
את המחלק המשותף המקסימלי של שני מספרים אפשר לחשב בנקל מתוך ה[[פירוק לגורמים של מספר שלם|פירוק לגורמים]] שלהם; כך לדוגמה המחלק המשותף המקסימלי של 495 ו-525 הוא 15, לפי החישוב:
<math>\ \mbox{gcd}(495,525)=\mbox{gcd}(3^2\cdot 5\cdot 11,3\cdot 5^2\cdot 7)=3\cdot 5=15</math>.
עם זאת, מציאת הפירוק לגורמים היא בעיה קשה, והרבה יותר קל מבחינה [[סיבוכיות|חישובית]] למצוא את המחלק המשותף המקסימלי ישירות, ללא חישוב הגורמים הראשוניים.
ה[[אלגוריתם אוקלידס|אלגוריתם של אוקלידס]] לחישוב המחלק המשותף המקסימלי הינו האלגוריתם הקדום ביותר שהופיע בכתב,
האלגוריתם מבוסס על אבחנה יסודית: לכל b,q,r, המחלקים המשותפים של b ושל r הם גם המחלקים המשותפים ל- b ול- bq+r. לפיכך, לשני הזוגות יש אותו מחלק משותף מקסימלי: <math>\ (qb+r,b)=(b,r)</math>.
שורה 74:
בכל [[חוג (מבנה אלגברי)|חוג]] קומוטטיבי אפשר להגדיר מחלקים: איבר a מחלק איבר b, אם קיים איבר t כך ש- b=ta. יחס החילוק שהוגדר כאן הוא מעין [[יחס סדר חלש]] (הוא אינו אנטי-סימטרי), ובעזרתו אפשר לדבר על "מחלק מקסימלי" גם בחוגים שאין בהם יחס סדר טבעי:
* איבר d הוא מחלק משותף מקסימלי של איברים a,b, אם d מחלק את a ואת b, וכל איבר המחלק את שניהם, מחלק את d.
הגדרה זו מתלכדת עם ההגדרה הרגילה, המתאימה רק ל[[חוג המספרים השלמים|חוג השלמים]].
להגדרה הכללית יש חיסרון אחד בולט: ברוב החוגים, ישנם זוגות של איברים שאין להם מחלק משותף מקסימלי. בעיה אחרת היא שהמחלק המשותף המקסימלי, אם קיים כזה, אינו יחיד; ההגדרה מבטיחה רק ששני מחלקים משותפים מקסימליים לאותם שני איברים, יחלקו זה את זה (איברים המחלקים זה את זה נקראים "ידידים"). מכיוון שאיברים ידידים יוצרים את אותו [[אידאל (אלגברה)|אידיאל]], אפשר לטפל בבעיה זו על ידי ניסוח ההגדרה בשפה של אידיאלים:
* האידיאל <math>\langle d\rangle</math> הוא מחלק משותף מקסימלי של a ו- b אם זהו האידיאל הראשי המינימלי המכיל את האידיאל <math>\langle a,b\rangle</math>.
ישנם [[תחום שלמות|תחומי שלמות]] מיוחדים, שבהם תמיד קיים מחלק משותף מקסימלי. אחת הדוגמאות היא [[תחום פריקות יחידה]]: בחוג כזה, אפשר לכתוב כל זוג איברים a ו- b כמכפלות <math>\ a=u p_1^{t_1}\dots p_n^{t_n}</math> ו- <math>\ b=v p_1^{s_1}\dots p_n^{s_n}</math>, כאשר u,v הפיכים ו- <math>\ p_1,\dots,p_n</math> הם ראשוניים של החוג, שאינם ידידים זה לזה. במקרה זה, המחלק המשותף המקסימלי הוא <math>\ p_1^{\min(t_1,s_1)}\dots p_n^{\min(t_n,s_n)}</math>.
מחלקה מיוחדת יותר של חוגים הם ה[[תחום ראשי|תחומים ראשיים]], המתאפיינים בכך שכל אידיאל הוא ראשי. בפרט, האידיאל הנוצר על ידי זוג איברים הוא אידיאל ראשי, והיוצר שלו הוא המחלק המשותף המקסימלי.
שורה 97:
==קישורים חיצוניים==
* [http://www.easycalculation.com/hcf.php מחשב מחלק משותף מקסימלי]
[[קטגוריה:תורת המספרים]]
| |||