מחלק משותף גדול ביותר של פולינומים

הגדרה

יהיו $f_1,\dots ,f_n\in F[x]$. פולינום מתוקן $g\in F[x]$ נקרא המחלק המשותף הגדול ביותר (ממג”ב) של $f_1,\dots ,f_n$ אם:

1. $g\mid f_i$ לכל $i$ (מחלק את כולם).
2. לכל $h\in F[x]$ המחלק את $f_1,\dots ,f_n$: $h\mid g$ (הגדול ביותר).

סימון: $g=\gcd (f_1,\dots ,f_n)$.

משפט קיום ויחידות

אם $f_1,\dots ,f_n\in F[x]$ לא כולם אפס, אז $\gcd (f_1,\dots ,f_n)$ קיים ויחיד. בנוסף, קיים ייצוג בזו:

$$\gcd (f_1,\dots ,f_n)=a_1{f}_1+\cdots +a_n{f}_n$$

(ייצוג כצירוף ליניארי — ייצוג בזו).

הוכחה (עבור $n=2$)

נגדיר את האידיאל:

$$I:=\{a{f}_1+b{f}_2:a,b\in F[x]\}$$

האידיאל $I$ אינו ריק (מכיל $f_1,f_2$). נבחר $g\in I$ ממעלה מינימלית שונה מאפס (קיים כי $f_1,f_2$ לא שניהם אפס). ניתן להניח ש-$g$ מתוקן (אחרת, נחלק במקדם המוביל; $I$ סגורה תחת כפל בסקלר, לכן $g$ המתוקן עדיין ב-$I$).

$g$ מחלק את $f_1$: נחלק עם שארית: $f_1=gq+r$ עם $\mathrm{deg}r<\mathrm{deg}g$. אז:

$$r=f_1-gq=f_1-(a{f}_1+b{f}_2)q=(1-aq)f_1+(-bq)f_2\in I$$

מהמינימליות של $\mathrm{deg}g$ (ו-$r\in I$), חייב $r=0$. לכן $g\mid f_1$. באופן דומה $g\mid f_2$.

$g$ הגדול ביותר: מכיוון ש-$g=a{f}_1+b{f}_2$, אם $h\mid f_1$ ו-$h\mid f_2$ אז $h\mid (a{f}_1+b{f}_2)=g$.

יחידות: נניח $g,g^{\prime }$ שניהם מקיימים את ההגדרה. אז $g\mid g^{\prime }$ וגם $g^{\prime }\mid g$. מכיוון ששניהם מתוקנים, $g=g^{\prime }$. $■$

פולינומים זרים

הפולינומים $f,g$ נקראים זרים (coprime) אם $\gcd (f,g)=1$. שקול: קיימים $a,b\in F[x]$ כך ש-$af+bg=1$.

טענה: אם $f$ אי-פריק ו-$f\nmid g$ אז $\gcd (f,g)=1$.

הוכחה: הממג”ב מחלק את $f$. כי $f$ אי-פריק, הממג”ב הוא $1$ או $f$. כי $f\nmid g$, הממג”ב אינו $f$, לכן הוא $1$. $■$

חישוב

ממג”ב מחשבים בעזרת אלגוריתם אוקלידס למציאת מחלק משותף מקסימלי.

ראה גם

• חלוקת פולינומים עם שארית
• אלגוריתם אוקלידס למציאת מחלק משותף מקסימלי
• פריקות יחידה בחוג הפולינומים