מחלק משותף מקסימלי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה מיישום נייד עריכה מאפליקציית אנדרואיד |
תגיות: עריכה ממכשיר נייד עריכה מיישום נייד עריכה מאפליקציית אנדרואיד |
||
שורה 70:
יעילות האלגוריתם זהה בסדר הגודל שלה ליעילות האלגוריתם הפשוט; מספר האיטרציות שמבצע האלגוריתם נותר זהה, ולכל איטרציה התווספו רק חישובים בסיסיים (מציאת q, חישוב m-qn).
==מחלק משותף
בכל [[חוג (מבנה אלגברי)|חוג]] קומוטטיבי אפשר להגדיר מחלקים: איבר a מחלק איבר b, אם קיים איבר t כך ש- b=ta. יחס החילוק שהוגדר כאן הוא מעין [[יחס סדר חלש]] (הוא אינו אנטי-סימטרי), ובעזרתו אפשר לדבר על "מחלק
* איבר d הוא מחלק משותף
הגדרה זו מתלכדת עם ההגדרה הרגילה, המתאימה רק ל[[חוג המספרים השלמים|חוג השלמים]].
להגדרה הכללית יש חיסרון אחד בולט: ברוב החוגים, ישנם זוגות של איברים שאין להם מחלק משותף
* האידיאל <math>\langle d\rangle</math> הוא מחלק משותף
ישנם [[תחום שלמות|תחומי שלמות]] מיוחדים, שבהם תמיד קיים מחלק משותף
מחלקה מיוחדת יותר של חוגים הם ה[[תחום ראשי|תחומים ראשיים]], המתאפיינים בכך שכל אידיאל הוא ראשי. בפרט, האידיאל הנוצר על ידי זוג איברים הוא אידיאל ראשי, והיוצר שלו הוא המחלק המשותף
בין התחומים הראשיים, ה[[חוג אוקלידי|חוגים האוקלידיים]] מתאפיינים בכך שאפשר לבצע בהם חילוק עם שארית. אלו הם בדיוק החוגים שבהם אפשר לממש את האלגוריתם של אוקלידס שתואר לעיל.
|