מחלק משותף מקסימלי – הבדלי גרסאות

המחלק המשותף המרבי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המרבי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המרבי של 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) נקראים [[מספרים זרים]] או "ראשוניים הדדית".

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

<math>\ \mbox{gcd}(495,525)=\mbox{gcd}(3^2\cdot 5\cdot 11,3\cdot 5^2\cdot 7)=3\cdot 5=15</math>.

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

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

ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על <math>\ \log_{\varphi}a</math> (כאן <math>\ \varphi</math> מסמן את [[יחס הזהב]]), כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המרבי של [[סדרת פיבונאצ'י|מספרי פיבונאצ'י]] עוקבים. מכאן שמציאת המחלק המשותף המרבי היא יעילה מבחינה חישובית; האלגוריתם פועל במהירות גם עבור מספרים גדולים, בני מאות ספרות.

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

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

* איבר <math>d</math> הוא מחלק משותף מרבי של איברים <math>a, b</math>, אם <math>d</math> מחלק את <math>a</math> ואת <math>b</math>, וכל איבר המחלק את שניהם, מחלק את <math>d</math>.

* האידיאל <math>\langle d\rangle</math> הוא מחלק משותף מרבי של <math>a</math> ו- <math>b</math> אם זהו האידיאל הראשי המזערי המכיל את האידיאל <math>\langle a,b\rangle</math>.

ישנם [[תחום שלמות|תחומי שלמות]] מיוחדים, שבהם תמיד קיים מחלק משותף מרבי. אחת הדוגמאות היא [[תחום פריקות יחידה]]: בחוג כזה, אפשר לכתוב כל זוג איברים <math>a</math> ו- <math>b</math> כמכפלות <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>, כאשר <math>u,v</math> הפיכים ו- <math>\ p_1,\dots,p_n</math> הם ראשוניים של החוג, שאינם ידידים זה לזה. במקרה זה, המחלק המשותף המרבי הוא <math>\ p_1^{\min(t_1,s_1)}\dots p_n^{\min(t_n,s_n)}</math>.