אלגוריתם אוקלידס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
|||
שורה 18:
בתכונה זו ניתן להשתמש בכיוון ההפוך - במקום להגדיל את אחד המספרים, מקטינים אותו: לכל זוג מספרים a,b, כאשר a הוא הגדול בין השניים, ניתן לחשב את ה[[שארית (חילוק)|שארית]] c מחלוקת a ב-b, כך ש-<math>a=c+qb, c<b</math>. מכאן מתקבל השוויון <math>\ (a,b) = (b,c)</math>, שבו הוחלף המספר הגדול a במספר c קטן יותר משני המספרים המקוריים, בלי לשנות את המחלק המשותף. אפשר להמשיך בתהליך שוב ושוב עם מספרים קטנים יותר ויותר, עד שמגיעים לזוג שאחד המספרים בו הוא 0; <math>(a,0)=a</math>, ולפיכך נמצא המחלק המשותף הגדול ביותר.
באופן [[רקורסיה|רקורסיבי]] ניתן להגדיר את האלגוריתם בצורה הבאה: לחישוב <math>(a,b)</math> {{כ}}(כאשר a>b), אם b הוא 0, התוצאה היא a. אחרת, חלק את a ב-b ומצא את השארית c; התוצאה היא <math>(b,c)</math> (
באופן כללי, ניתן להשתמש באלגוריתם בכל [[חוג אוקלידי]]. כך לדוגמה ניתן להשתמש באלגוריתם כדי למצוא את המחלק המשותף המקסימלי של שני [[פולינום|פולינומים]] מעל [[שדה (מבנה אלגברי)|שדה]].
|