אלגוריתם אוקלידס למציאת מחלק משותף מקסימלי

הרעיון

נשתמש בעובדה: $g cd (f, g) = g cd (g, r)$ כאשר $f = g q + r$ . לכן ניתן להחליף את הזוג $(f, g)$ ב- $(g, r)$ עם שארית קטנה יותר, עד לשארית אפס.

קלט: $f, g \in F [x]$ עם $g \neq = 0$ .

שלבים:

חלק $f$ ב- $g$ : מצא $q_{1}, r_{1}$ עם $f = g q_{1} + r_{1}$ , $de g r_{1} < de g g$ .
אם $r_{1} = 0$ : $g cd (f, g) = g$ מתוקן. עצור.
אחרת: הצב $f_{1} = g$ , $g_{1} = r_{1}$ וחזור לשלב 1 עם $(f_{1}, g_{1})$ .

סיום: הסדרה $de g g > de g r_{1} > de g r_{2} > \dots \geq 0$ יורדת, ולכן האלגוריתם מסתיים.

הפלט: הממג”ב הוא השארית האחרונה שאינה אפס, מתוקנת.

g cd (f, g) = g cd (g, r_{1}) = g cd (r_{1}, r_{2}) = \dots

כי: אם $d ∣ f$ ו- $d ∣ g$ אז $d ∣ (f - g q_{1}) = r_{1}$ , ולהפך.

נחשב $g cd (30, 18)$ :

301812 = 1 \cdot 18 + 12 = 1 \cdot 12 + 6 = 2 \cdot 6 + 0

לכן $g cd (30, 18) = 6$ .

נחשב $g cd (x^{3} - 1, x^{2} - 1)$ מעל $Q$ :

x^{3} - 1 x^{2} - 1 = (x^{2} - 1) \cdot x + (x - 1) = (x - 1) \cdot (x + 1) + 0

לכן $g cd (x^{3} - 1, x^{2} - 1) = x - 1$ .

בדיקה: $x^{3} - 1 = (x - 1) (x^{2} + x + 1)$ ו- $x^{2} - 1 = (x - 1) (x + 1)$ . אכן $x - 1$ הוא המחלק המשותף הגדול.

ניתן להעלות בסדר הפוך כדי לכתוב $g cd (f, g) = a f + b g$ :

מהדוגמה: $x - 1 = (x^{3} - 1) - x \cdot (x^{2} - 1)$ , כלומר $a = 1$ , $b = - x$ .