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

תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה מיישום נייד עריכה מאפליקציית אנדרואיד
תגיות: עריכה ממכשיר נייד עריכה מיישום נייד עריכה מאפליקציית אנדרואיד
שורה 70:
יעילות האלגוריתם זהה בסדר הגודל שלה ליעילות האלגוריתם הפשוט; מספר האיטרציות שמבצע האלגוריתם נותר זהה, ולכל איטרציה התווספו רק חישובים בסיסיים (מציאת q, חישוב m-qn).
 
==מחלק משותף מקסימלימרבי בתחומי שלמות כלליים==
 
בכל [[חוג (מבנה אלגברי)|חוג]] קומוטטיבי אפשר להגדיר מחלקים: איבר 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>.
 
מחלקה מיוחדת יותר של חוגים הם ה[[תחום ראשי|תחומים ראשיים]], המתאפיינים בכך שכל אידיאל הוא ראשי. בפרט, האידיאל הנוצר על ידי זוג איברים הוא אידיאל ראשי, והיוצר שלו הוא המחלק המשותף המקסימליהמרבי.
 
בין התחומים הראשיים, ה[[חוג אוקלידי|חוגים האוקלידיים]] מתאפיינים בכך שאפשר לבצע בהם חילוק עם שארית. אלו הם בדיוק החוגים שבהם אפשר לממש את האלגוריתם של אוקלידס שתואר לעיל.